位置: 编程技术 - 正文

javascript常用经典算法实例详解(js常用方法总结)

编辑:rootadmin

推荐整理分享javascript常用经典算法实例详解(js常用方法总结),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:javascript常用类型,javascript常用语句,javascript的常用例子,javascript常用语法,javascript常用语法,javascript的常用例子,javascript常用类型,javascript常用语句,内容如对您有帮助,希望把文章链接给更多的朋友!

本文实例讲述了javascript常用算法。分享给大家供大家参考,具体如下:

入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld

二分查找(又称折半查找) - 适用于已排好序的线性结构 - 时间复杂度O(logN)

冒泡排序 -- 时间复杂度O(n^2)

选择排序 -- 时间复杂度O(n^2)

插入排序 -- 时间复杂度O(n^2)

字符串反转 -- 时间复杂度O(logN)

关于稳定性排序的一个结论:

基于比较的简单排序算法,即时间复杂度为O(N^2)的排序算法,通常可认为均是稳定排序其它先进的排序算法,比如归并排序、堆排序、桶排序之类(通常这类算法的时间复杂度可优化为n*LogN),通常可认为均是不稳定排序

单链表实现

关于邻接矩阵、邻接表的选择:

邻接矩阵、邻接表都是图的基本存储方式,稀松图情况下(即边远小于顶点情况下),用邻接表存储比较适合(相对矩阵N*N而言,邻接表只存储有值的边、顶点,不存储空值,存储效率更高)稠密图情况下(即边远大地顶点情况下),用邻接矩阵存储比较适合(数据较多的情况下,要对较做遍历,如果用链表存储,要经常跳来跳去,效率较低)

堆:

几乎完全的二叉树:除了最右边位置上的一个或几个叶子可能缺少的二叉树。在物理存储上,可以用数组来存储,如果A[j]的顶点有左、右子节点,则左节点为A[2j]、右节点为A[2j+1],A[j]的父顶点存储在A[j/2]中

堆:本身是一颗几乎完全的二叉树,而且父节点的值不小于子节点的值。应用场景:优先队列,寻找最大或次最大值;以及把一个新元素插入优先队列。

注:以下所有讨论的堆,约定索引0处的元素仅占位,有效元素从下标1开始

根据堆的定义,可以用以下代码测试一个数组是否为堆:

节点向上调整siftUp

某些情况下,如果堆中的某个元素值改变后(比如 ,8,9,7 变成 ,8,9, 后,需要向上调整 ),不再满足堆的定义,需要向上调整时,可以用以下代码实现

节点向下调整siftDown (既然有向上调整,自然也有向下调整)

向堆中添加新元素

从堆中删除元素

堆排序:

这是一种思路非常巧妙的排序算法,精华在于充分利用了“堆”这种数据结构本身的特点(首元素必然最大),而且每个元素的上移、下调,时间复试度又比较低,仅为O(logN),空间上,也无需借助额外的存储空间,仅在数组自身内部交换元素即可。

思路:

1、先将首元素(即最大元素)与最末尾的元素对调---目的在于,把最大值沉底,下一轮重就不再管它了2、经过1后,剩下的元素通常已经不再是一个堆了。这时,只要把新的首元素用siftDown下调,调整完以后,新的最大值元素自然又上升到了首元素的位置3、反复1、2,大的元素逐一沉底,最后整个数组就有序了。时间复杂度分析:创建堆需要O(n)的代价,每次siftDown代价为O(logN),最多调整n-1个元素,所以总代价为 O(N) + (N-1)O(logN),最终时间复杂度为O(NLogN)

关于建堆,如果明白其中的原理后,也可以逆向思路,反过来做

javascript常用经典算法实例详解(js常用方法总结)

不相交集合查找、合并

归纳法:

先来看二个排序的递归实现

递归的程序通常易于理解,代码也容易实现,再来看二个小例子:

从数组中,找出最大值

有一个已经升序排序好的数组,检查数组中是否存在二个数,它们的和正好为x ?

递归程序虽然思路清晰,但通常效率不高,一般来讲,递归实现,都可以改写成非递归实现,上面的代码也可以写成:

递归并不总代表低效率,有些场景中,递归的效率反而更高,比如计算x的m次幂,常规算法,需要m次乘法运算,下面的算法,却将时间复杂度降到了O(logn)

当然,这其中并不光是递归的功劳,其效率的改进 主要依赖于一个数学常识: x^m = [x^(m/2)]^2,关于这个问题,还有一个思路很独特的非递归解法,巧妙的利用了二进制的特点

再来看看经典的多项式求值问题:

给定一串实数An,An-1,...,A1,A0 和一个实数X,计算多项式Pn(x)的值

著名的Horner公式:

已经如何计算:

显然有:

这样只需要 N次乘法+N次加法

多数问题:

一个元素个数为n的数组,希望快速找出其中大于出现次数>n/2的元素(该元素也称为多数元素)。通常可用于选票系统,快速判定某个候选人的票数是否过半。最优算法如下:

以上算法基于这样一个结论:在原序列中去除两个不同的元素后,那么在原序列中的多数元素在新序列中还是多数元素

证明如下:

如果原序列的元素个数为n,多数元素出现的次数为x,则 x/n > 1/2去掉二个不同的元素后,a)如果去掉的元素中不包括多数元素,则新序列中 ,原先的多数元素个数/新序列元素总数 = x/(n-2) ,因为x/n > 1/2 ,所以 x/(n-2) 也必然>1/2b)如果去掉的元素中包含多数元素,则新序列中 ,原先的多数元素个数/新序列元素总数 = (x-1)/(n-2) ,因为x/n > 1/2 =》 x>n/2 代入 (x-1)/(n-2) 中,有 (x-1)/(n-2) > (n/2 -1)/(n-2) = 2(n-2)/(n-2) = 1/2

下一个问题:全排列

分治法:

要点:将问题划分成二个子问题时,尽量让子问题的规模大致相等。这样才能最大程度的体现一分为二,将问题规模以对数折半缩小的优势。

split算法的思想应用:

设A[1..n]是一个整数集,给出一算法重排数组A中元素,使得所有的负整数放到所有非负整数的左边,你的算法的运行时间应当为Θ(n)

希望本文所述对大家JavaScript程序设计有所帮助。

javascript数据结构之二叉搜索树实现方法 本文实例讲述了javascript二叉搜索树实现方法。分享给大家供大家参考,具体如下:二叉搜索树:顾名思义,树上每个节点最多只有二根分叉;而且左分

js获取图片宽高的方法 本文分享多种js获取图片宽高的方法,并且通过实例进行分析,希望大家从中有所收获。一、简陋的获取图片方式//图片地址后面加时间戳是为了避免缓

javascript数据结构之双链表插入排序实例详解 本文实例讲述了javascript数据结构之双链表插入排序实现方法。分享给大家供大家参考,具体如下:数组存储前提下,插入排序算法,在最坏情况下,前

标签: js常用方法总结

本文链接地址:https://www.jiuchutong.com/biancheng/385506.html 转载请保留说明!

上一篇:javascript实现很浪漫的气泡冒出特效(javascript怎么样)

下一篇:javascript数据结构之二叉搜索树实现方法(javascript数据结构与算法)

  • 简易计税方法和免税该怎么选择
  • 开承兑汇票的条件 费用
  • 收到失业金返还什么意思
  • 福利费是计提还是结转
  • 报个税的工资表
  • 运输费增值税专用发票几个点
  • 去年的增值税普票能作废吗?
  • 包装设置图片
  • 会议收入包括哪些
  • 产生的信息服务有哪些
  • 房产公司增值税和土地增值税
  • 月末结转所有收入类账户
  • 机械设备租赁征求意见稿
  • 厂房出租税收分类
  • 实收资本未注明投资款
  • 外地出差的餐费住宿费是不是都计入差旅费
  • 购入二手设备,无发票怎么记账
  • 企业购买设备可以税前扣除吗
  • 外贸企业出口退税申报期限
  • 企业的不征税收入用于支出所形成的资产,其计算的折旧
  • 包装物怎么入账
  • 坏账准备金最新计算公式
  • 固定资产出售是否属于日常关联交易
  • 用友软件以前年度损益调整报表勾稽关系不对
  • 企业风险报酬转移怎么理解
  • 在windows 10中
  • 出口退税率和进项一致吗
  • 设置ahci模式后,开不了机
  • php遍历显示多维数组
  • win10 dev版本
  • 把原材料给别人加工怎么入账
  • 专项维修基金会产生利息吗
  • 苹果14数据线
  • php array数组
  • php图片链接
  • 特许权使用费20%
  • vue3使用教程
  • websocket怎么读
  • 财务支出表怎么做
  • 预缴税款表怎么打印出来
  • 开票和不开票的销项税额怎么算
  • el-form表单
  • 企业车辆年检费多少钱
  • 金融债券利息收入免企业所得税吗
  • 车改补贴算工资吗
  • 应交税费增值税销项税
  • 如何判断固定资产已提足折旧
  • 发票的类型分为哪几类
  • 增值税发票系统客服电话
  • 公司买车可以抵扣企业所得税吗
  • 研发费用账务处理一定在管理费用吗
  • 少数股东权益如何保障
  • 退休人员基本养老金包括哪些
  • 机动车转让后未过户原车主要承担赔偿责任
  • 双倍余额递减法例题及解析
  • 独立核算的单位是什么意思
  • 对于事业单位无力支付的银行承兑汇票
  • 会计怎么做工资单
  • 忘记MySQL的root密码该怎么办
  • xp关机会自动重新启动
  • ubuntu如何安装
  • 笔记本搜索功能用不了
  • win10怎么更改磁盘空间分配
  • centos查看inode
  • win7电脑怎么设置自动锁屏
  • windows7怎么解除密码
  • win8怎么切换界面
  • 简单谈谈对中国电信的认识
  • 搭建gitbook
  • perl $?
  • linux分区类型默认的是什么
  • shell脚本 -ne 0
  • unity mesh编程
  • python编程内容
  • 财政票据和税务票据的法律效力一样吗
  • 融资租赁利息是哪个科目
  • 地税怎么查个人所得税
  • 长期挂账的其他应付款的规定
  • 税控ic卡就是税控盘吗
  • 国家税务总局河南省税务干部学校
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设