位置: 编程技术 - 正文
javascript常用经典算法实例详解(js常用方法总结)
发布时间：2024-02-27推荐整理分享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)
关于建堆，如果明白其中的原理后，也可以逆向思路，反过来做
不相交集合查找、合并
归纳法：
先来看二个排序的递归实现
递归的程序通常易于理解，代码也容易实现，再来看二个小例子：
从数组中，找出最大值
有一个已经升序排序好的数组，检查数组中是否存在二个数，它们的和正好为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 转载请保留说明！
