关于javascript:数据结构与算法复杂度分析

1. 如何剖析 & 统计算法的执行效率和资源耗费?
- 1.1. 大 O 复杂度表示法
- 1.2. 工夫复杂度剖析
- 1.3. 常见工夫复杂度实例剖析
  - 1.3.1. O(1) 常量阶
  - 1.3.2. O(logn) 对数阶 & O(nlogn)线性对数阶
  - 1.3.3. O(m+n) & O(m*n)
- 1.4. 附加
- 1.5. 空间复杂度剖析
2. 小结
3. 思考与探讨
4. 浅析最好、最坏、均匀、均摊工夫复杂度
- 4.1. 均摊工夫复杂度
- 4.2. 附加问题

参考：

极客工夫：数据结构与算法之美

《数据结构》——胡学钢（合肥工业大学）

掂量算法的次要性能指标包含工夫性能和空间性能。

为了使算法的工夫复杂度便于比拟，个别不宜采纳某个具体机器上的运行工夫的模式示意，而是以算法中根本语句的执行次数来掂量，然而在理论利用中执行次数也是难以掂量的，所以进一步采纳 根本语句的执行次数的数量级 来示意。

T(n) = O (f(n) )

T(n)代表代码执行工夫，O 就是工夫复杂度，示意代码执行工夫与 f(n)表达式成正比。n 代表数据规模的大小，f(n)是一个表达式，示意每行代码执行的次数总和。

下面的式子就是大 O 工夫复杂度表示法，实际上它并不能代表代码真正的执行工夫，而是示意代码执行工夫随数据规模增长的变化趋势，也称作渐进工夫复杂度，简称工夫复杂度。

当 n 的量级很大，那么 f(n)表达式中的 低阶、常量、系数 就能够省略，因为他们并不左右增长趋势，故能够疏忽。此时 T(n) = O(2n+2) 写成 T(n) = O(n)，T(n) = O(2n²+2n+3)写成 T(n) = O(n²)。

这外面一个重要的点就是即使一段代码执行次数很多，对执行工夫影响很大，然而执行次数已知时，它就是能够疏忽，因为它并不左右增长趋势。所以不论常量的执行工夫多大，咱们都能够疏忽掉。

如何进行工夫复杂度剖析呢？

只关注循环执行次数最多的那段代码，这段外围代码执行次数的 n 的量级，就是整段要剖析代码的工夫复杂度。
加法法令：总复杂度等于量级最大的那段代码的复杂度。如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n) = T1(n) + T2(n) = max(O(f(n)),O(g(n))) = O(max(f(n),g(n)))。
乘法法令：嵌套的代码的复杂度等于嵌套内外代码复杂度的乘积。如果 T1(n)=O(f(n) )，T2(n)=O(g(n) )；那么 T(n) = T1(n)*T2(n) = O(f(n))*O(g(n)) = O(f(n)*g(n)) 或者说 T1(n) = O(n)，T2(n) = O(n2)，则 T1(n) * T2(n) = O(n³)。

复杂度	阶层
O(1)	常量阶
O(logn)	对数阶
O(n)	线性阶
O(nlogn)	线性对数阶
O(n²)	平方阶
…	…
O(n^k)	k 次方阶
O(2ⁿ)	指数阶
O(n!)	阶乘阶

下面的阶能够分为多项式量级和非多项式量级，最初两种就是非多项式量级。当 n 的规模越来越大，非多项式量级算法的执行工夫会急剧减少，是低效的算法，所以不探讨其工夫复杂度。

它并不代表只执行了一次，这只是示意常量级工夫复杂度的一种办法。
只有代码的执行工夫不随 n 的增大而增大，则这样代码的工夫复杂度都记为 O(1)。个别状况下，只有算法中不存在循环语句、递归语句，即便有成千上万行的代码，其工夫复杂度也是 Ο(1)。

    i=1;
    while (i <= n)  {i = i * p;}

i = i * p;这行代码执行了多少次？先看 i 的取值是一个等比数列：

p⁰,p¹,p²…p^k…p^x = n，
恰好 x 代表了代码执行次数，x = log_pn，实际上不论底数是多少，咱们都能够把所有对数阶的工夫复杂度都记为 O(logn)，为什么？

举个例子：log₃n 就等于 log₃2 log₂n，所以 O(log₃n) = O(C log₂n)，再疏忽系数就能够失去 O(log₃n) = O(log₂n)，因而在对数阶工夫复杂度的示意办法里能够间接疏忽底对立标识为 O(logn)。

O(nlogn)线性对数阶同理，即一段时间复杂度为 O(logn)的代码执行了 n 遍。

归并排序、疾速排序的工夫复杂度都是 O(nlogn)。

当代码的工夫复杂度由两个数据的规模来决定。

    function cal(m, n) {
        let sum_1 = 0;
        let i = 1;
        for (; i < m; ++i) {sum_1 = sum_1 + i;}

        let sum_2 = 0;
        let j = 1;
        for (; j < n; ++j) {sum_2 = sum_2 + j;}
        console.log(sum_1 + sum_2);

    }
    cal(3, 4);

其工夫复杂度就是 O(m+n)，因为咱们无奈评估 m、n 谁大谁小，所以在此咱们不能简略地应用加法法令，不能省略其中一个。能够把加法法令改成：T1(m) + T2(n) = O(f(m) + g(n))。然而乘法法令持续无效：T1(m) * T2(n) = O(f(m) * f(n))。

同理，空间复杂度全称 渐进空间复杂度 ， 示意算法的存储空间与数据规模之间的增长关系，据说空间复杂度的剖析比工夫复杂度的简略，同样常量阶的空间存储能够疏忽，因为它和数据规模 n 没有关系。

常见的空间复杂度就是 O(1)、O(n)、O(n²)，其余的像 O(logn)、O(nlogn)这样的空间复杂度根本用不上。

复杂度包含工夫复杂度与空间复杂度，用来剖析算法的执行效率与数据规模之间的增长关系。常见的复杂度其实就那几个，O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。

【例 1】在我的项目之前都会进行性能测试，再做代码的复杂度剖析，这是否多此一举，剖析复杂度又有什么意义？

答复 1：复杂度剖析为咱们提供了实践剖析的方向，并且它是宿主平台无关的，可能让咱们对咱们的程序或算法有一个大抵的意识，让咱们晓得，比方在最坏的状况下程序的执行效率如何，同时也为咱们交换提供了一个不错的桥梁，咱们能够说，算法 1 的工夫复杂度是 O(n)，算法 2 的工夫复杂度是 O(logN)，这样咱们立即就对不同的算法有了一个“效率”上的感性认识。

答复 2：性能测试更多的是一种试验后果。而复杂度剖析，能够帮忙咱们剖析内因

答复 3：1、性能测试是依附于具体的环境，如 SIT、UAT 机器配置及实例数量不统一后果也有差异。
2、复杂度剖析是独立于环境的，能够大抵估算出程序所执行的效率。

答复 4：有必要，基准测试是预先，也是实践验证，有时候 O(n)未必肯定比 O(1)效率低。
复杂度剖析是实践，整体趋势上反馈了一个算法的工夫或者空间利用率与数据规模的渐进关系，并且像程序员之间应用设计模式来探讨代码设计一样，说出名字就大抵晓得代码是如何组织的，大 O 也是一样。
随着本人应用大 O 剖析代码复杂度的熟练程度减少，判断一段代码的复杂度可能分分钟

【例 2】什么是复杂度剖析？

1. 数据结构和算法解决“如何让计算机更快工夫、更省空间的解决问题”。
2. 因而需从执行工夫和占用空间两个维度来评估数据结构和算法的性能。
3. 别离用工夫复杂度和空间复杂度两个概念来形容性能问题，二者统称为复杂度

【例 3】存储一个二进制数，输出规模（空间复杂度）是 O(logn) bit。请问如何了解

比方 8 用二进制示意就是 3 个 bit。16 用二进制示意就是 4 个 bit。以此类推 n 用二进制示意就是 log₂n，可写为 logn 个 bit。

    let arr = [2, 4, 7, 4, 6, 7, 2, 3, 0];

    function find(array, x) {
        let i = 0;
        let pos = -1;
        for (; i < array.length; ++i) {if (array[i] == x) {
                pos = i;
                break;
            }
        }
        console.log(pos);
    }
    find(arr, 6);

如上代码求的是指定的数字 x 在无序数组数组中呈现的地位。依照之前的分析方法，这段代码工夫复杂度如同是 O(n)，然而显著代码的执行次数不肯定是 n 次，如果要查找的 x 呈现在第一位，那么工夫复杂度就应该是 O(1)，如果呈现在最初一位才应该是 O(n)，这时候上文讲的分析方法就不足以应酬这样的问题了。

引入三个概念：最好状况工夫复杂度、最坏状况工夫复杂度和均匀状况工夫复杂度。

其中最好最坏工夫复杂度很好了解，均匀复杂度指的就是均匀状况下的复杂度。

假如数组有 n 个元素，元素 x 在数组中的地位状况总共有 n 种，再加上不在其中的状况，总共有 n + 1 种，由此每次遍历数组元素的个数也有 n + 1 种状况，把他们加起来除以 n + 1 就失去遍历的均匀个数，计算如下：

1+2+3+...+n+n / n+1 = n(n+3) / 2(n+1)

而后疏忽常量，系数，可得工夫复杂度就是 O(n)，不过此处依然存在问题，因为没有思考 x 呈现的某个中央的概率，假如不再数组中的概率是 1 /2，那么呈现在数字中某个地位上的概率就是 1 /2n，计算如下：

1 ✖ 1/2n + 2 ✖ 1/2n + 3 ✖ 1/2n + … + n ✖ 1/2n + n ✖ 1/2 = 3n + 1 / 4

最初一项的 n ✖ 1/2 代表须要查找 n 次，最初才发现不在数组中。

在概率论中这叫冀望，就是平均值，不过这里示意进去工夫复杂度依然是 O(n)。

听起来和下面讲的均匀复杂度很像，通过我的理解这外面有一种一种取多补少的思维，下面讲到的均匀复杂度就是赤裸裸的数学冀望的玩法，而这个均摊工夫复杂度和他很像但又不是，因为咱们并不一定要通过数学演算求进去，举个例子:

   let n = 3,
      count = 0,
      array = (new Array(n)).fill(0);

   function insert(val) {if (count == array.length) { // 数组元素插满了
         let sum = 0;
         for (let i = 0; i < array.length; ++i) { // 对数组元素求和后果放到第一位，再从数组第二位开始插
            sum = sum + array[i];
         }
         array[0] = sum;
         count = 1;
      }
      array[count] = val;
      ++count;
   }

这段代码要做的是向一个数组中插入数据，数组初始化为填充 0 的数组，长度为 n，有以下规定：

count 记录以后插入的地位，如果数组曾经插满了，就对以后数组元素求和并把求和后果放在数组第一位，而后从第 2 位开始持续插入
如果数组未满，则间接依照 count 插入即可

剖析可知 n 为数组长度，插入时有 n 种可能状况，0~n- 1 时直接插入，工夫复杂度为 O(1)；当数组满时 count == n，这时候须要额定的操作求数组元素之和，工夫复杂度为 O(n)。依据加权均匀的计算方法可得：

即使 count == n 时呈现了复杂度为 O(n)的操作，然而整段代码的工夫复杂度却依然是 O(1)，针对这样在极其状况下工夫复杂度才为 O(n)并且其复杂度的呈现有肯定程序关系的代码，咱们引入了一种更加简略的分析方法：摊还分析法。

像下面的例子，每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，这是一个有法则可循的插入，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组间断的操作的均摊工夫复杂度就是 O(1)。这就是均摊剖析的大抵思路。

均摊复杂度用到的不多，具体情况具体分析，只需明确摊还分析法的思路即可。

对一个数据结构进行一组间断操作中，大部分状况下工夫复杂度都很低，只有个别情况下工夫复杂度比拟高，而且这些操作之间存在前后连贯的时序关系，这个时候，咱们就能够将这一组操作放在一块儿剖析，看是否能将较高工夫复杂度那次操作的耗时，平摊到其余那些工夫复杂度比拟低的操作上。而且，在 可能利用均摊工夫复杂度剖析的场合，个别均摊工夫复杂度就等于最好状况工夫复杂度，能够认为均摊工夫复杂度就是一种非凡的均匀工夫复杂度。

【例】剖析如下代码的工夫复杂度，其中 len 应是一个未知量，在这里取 10 不便了解

    // 全局变量，大小为 10 的数组 array，长度 len，下标 i。let array = new Array(10);
    let len = 10; //len 是一个不确定的量
    let i = 0;

    // 往数组中增加一个元素
    function add(element) {if (i >= len) { // 数组空间不够了
            // 从新申请一个 2 倍大小的数组空间
            let new_array = new Array(len * 2);
            // 把原来 array 数组中的数据顺次 copy 到 new_array
            for (let j = 0; j < len; ++j) {new_array[j] = array[j];
            }
            // new_array 复制给 array，array 当初大小就是 2 倍 len 了
            array = new_array;
            len = 2 * len;
        }
        // 将 element 放到下标为 i 的地位，下标 i 加一
        array[i] = element;
        ++i;
    }

思考摊还剖析的时候想一想应该向前还是向后摊派？

【答】

最好状况数组不必扩容，直接插入即可，工夫复杂度为 O（1）
最坏状况，数组须要扩容，那么扩容那次的工夫复杂度为 O（n），其中 n 就是以后数组长度，也是数组元素的个数。
依照摊还分析法看，均摊工夫复杂度应该是 O（1），这一点不好了解，因为不想下面的 insert 那样刚好摊派，不过你列出前 40 位的插入示意图就能够明确，尽管每次数组都是倍数增长，也就是说越到前面扩容的越厉害，然而 O(1)的数量也越来越多，也就摊派地越多，每次一须要扩容的时候都要向后摊派原数组 长度 次，恰好是 2 倍扩容，所以刚好摊派。。。算了，还是本人列个图清晰。

1. 如何剖析 & 统计算法的执行效率和资源耗费?

1.1. 大 O 复杂度表示法

1.2. 工夫复杂度剖析

1.3. 常见工夫复杂度实例剖析

1.3.1. O(1) 常量阶

1.3.2. O(logn) 对数阶 & O(nlogn)线性对数阶

1.3.3. O(m+n) & O(m*n)

1.4. 附加

1.5. 空间复杂度剖析

2. 小结

3. 思考与探讨

4. 浅析最好、最坏、均匀、均摊工夫复杂度

4.1. 均摊工夫复杂度

4.2. 附加问题