JavaScript 排序算法基础：时间复杂度与空间复杂度详解

排序算法基础与分类

排序算法的介绍

排序算法（Sort Algorithm）是指将一组数据按照指定的顺序进行排列的过程。

排序的分类

内部排序：指将所有需要处理的数据加载到内部存储器（内存）中进行排序。

外部排序法：当数据量过大无法全部加载到内存时，需借助外部存储（如文件）进行排序。

常见的排序算法分类

时间复杂度分析方法

算法的时间复杂度用于度量程序（算法）执行时间的两种方法。

1、事后统计法：该方法可行，但存在两个问题：首先，评估算法性能需要实际运行程序；

其次，统计结果依赖于计算机的硬件和软件环境，只有在相同机器和状态下运行才能比较算法速度。

2、事前估算法：通过分析算法的时间复杂度来判断哪个算法更优。

时间频度

时间频度：算法花费的时间与语句执行次数成正比，执行次数越多耗时越长。语句执行次数称为语句频度或时间频度，记为T(n)。

举例说明-基本案例

例如计算1到100所有数字之和，我们可以设计两种不同的算法。

常见时间复杂度详解

时间复杂度

1、一般情况下，算法基本操作语句的重复执行次数是问题规模n的函数，记为T(n)。若存在辅助函数f(n)，使得当n趋近无穷大时，T(n)/f(n)的极限值为非零常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，其中O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

2、T(n)不同，但时间复杂度可能相同。例如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2，尽管T(n)不同，但时间复杂度均为O(n²)。

3、计算时间复杂度的方法：

用常数1替换所有加法常数，T(n)=n²+7n+6 变为 T(n)=n²+7n+1；仅保留最高阶项，T(n)=n²+7n+1 变为 T(n)=n²；去除最高阶项系数，T(n)=n² 变为 T(n)=n²，最终得到时间复杂度为O(n²)。

说明：

常见的算法时间复杂度由小到大依次为： Ο(1)＜Ο(log 2 n)＜Ο(n)＜Ο(nlog 2 n)＜Ο(n 2 )＜Ο(n 3 )＜ Ο(n k ) ＜Ο(2 n ) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低

从图中可见，应尽可能避免使用指数阶的算法。

时间复杂度示例介绍 1）常数阶O(1)

只要代码没有循环等复杂结构，无论执行多少行，时间复杂度均为O(1)。

若代码执行耗时不随变量增长而增加，即使代码长达数万或数十万行，也可用O(1)表示其时间复杂度。

2）对数阶O(log₂n)

在while循环中，每次将i乘以2，使i逐渐接近n。假设循环x次后i大于2的x次方等于n，则x=log₂n，即循环log₂n次后代码结束，时间复杂度为O(log₂n)。注意，若改为i=i*3，则时间复杂度为O(log₃n)，底数随代码变化。

3）线性阶O(n)

若for循环执行n遍，耗时随n变化，此类代码的时间复杂度用O(n)表示。

4）线性对数阶O(nlogN)

线性对数阶O(nlogN)易于理解：将时间复杂度为O(logn)的代码循环N遍，时间复杂度即为n*O(logN)，也就是O(nlogN)。

5）平方阶O(n²)

若将O(n)的代码再嵌套循环一遍，时间复杂度为O(n²)。例如嵌套2层n循环，时间复杂度为O(n*n)，即O(n²)。若将其中一层循环的n改为m，则时间复杂度变为O(m*n)。

6）立方阶O(n³)、K次方阶O(n^k）

理解方式参考O(n²)，O(n³)相当于三层n循环，其他类似。

平均与最坏复杂度及空间复杂度

平均时间复杂度和最坏时间复杂度：平均时间复杂度指所有可能输入实例以等概率出现时的算法运行时间。最坏情况下的时间复杂度称为最坏时间复杂度，通常讨论的时间复杂度即为此值，因为它是算法在任何输入实例上运行时间的界限，保证运行时间不会超过最坏情况。平均与最坏复杂度是否一致取决于算法（如图）。

算法的空间复杂度简介：类似于时间复杂度，空间复杂度（Space Complexity）定义为算法耗费的存储空间，也是问题规模n的函数。它衡量算法运行过程中临时占用存储空间的大小。部分算法临时工作单元数随n增大而增大，如快速排序和归并排序。算法分析主要讨论时间复杂度，因为用户更看重执行速度。一些缓存产品（如redis、memcache）和算法（如基数排序）本质是用空间换时间。

总结

以上介绍了JavaScript中数据结构与算法的排序算法实例详解，希望对大家有所帮助。如有疑问请留言，小编会及时回复。感谢大家对本站的支持！ 若本文对您有帮助，欢迎转载，请注明出处，谢谢！