为什么需要复杂度分析
我们可以把代码跑一遍，然后通过一些工具来统计、监控就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？
首先，肯定的说这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字，叫事后统计法。但是这种统计方法存在一定的局限性。
1、测试结果依赖测试的环境以及数据规模的影响
比如，我们拿同样一段代码，再不同的机器以及不同的数据规模可能会有不同的结果。
2、掌握复杂度分析，将能编写出性能更优的代码
所以我们需要一个不用具体的测试环境、测试数据来测试，就可以粗略地估计算法的执行效率的方法，这就是我们需要的时间、空间复杂度分析方法。
复杂度分析提供了一个粗略的分析模型，与实际的性能测试并不冲突，更不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维，有助于产出效率高的代码。
大 O 复杂度表示法
算法的执行效率，简单的说就是代码执行的时间。但是怎么样在不运行代码的情况下，用"肉眼"得到一段代码的执行时间呢？这里有段非常简单的代码，求 1,2,3...n 的累加和。现在来估算一下这段代码的执行时间。
1 function countSum(n) {2 let sum = 0;3 console.log(n)4 for (i = 0; i <= n; ++i) {5 sum = sum + i;6 }7 return sum;8 }每行代码对应的 CPU 执行的个数、执行的时间都不一样，所以只是粗略估计，我们可以假设每行代码执行的时间都一样为 unit_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？
第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n * unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+2) * unit_time。
尽管我们不知道 unit_time 的具体值，但是通过代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是所有代码的执行时间 T(n) 与代码的执行次数 f(n) 成正比。
我们可以把这个规律总结成一个公式，这个公式就是数据结构书上说的大O表示法。
我来具体解释一下这个公式：
- T(n) 表示代码执行的时间
- n 表示数据规模的大小
- f(n) 表示代码执行的次数总和
因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
所以，上面例子中的 T(n) = O(2n+2)，这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
时间复杂度分析
分析大O一般的步骤如下：
- 用常数1代替运行中的所有的加法常数 n + 2 + 3 + 4 等于 n + 1
- 在修改后的运行次数函数中，只保留最高阶项 如 n^3 + n^2 等于 n^3
- 如果最高阶项存在且不为1，则去掉与这个项相乘的常数 如 3n^2 等于 n^2
通过上面三个步骤可以总结出几个方法
1. 只关注循环执行次数最多的一段代码
大 O 这种复杂度表示方法只是表示一种变化趋势。通过上面的公式我们会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级。所以我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。
2.加法法则：总复杂度等于量级最大的那段代码的复杂度
如果是很长的一个代码段，可以把他们拆分计算时间复杂度，然后再加起来
1 function countSum(n) { 2 let sum_1 = 0; 3 console.log('计算：sum_1') 4 for (let p = 0; p < 100; ++p) { 5 sum_1 = sum_1 + p; 6 } 7 8 let sum_2 = 0; 9 console.log('计算：sum_2')10 for (let q = 0; q < n; ++q) {11 sum_2 = sum_2 + q;12 }13 14 let sum_3 = 0;15 console.log('计算：sum_3')16 for (let i = 0; i <= n; ++i) {17 j = 1; 18 for (let j = 0; j <= n; ++j) {19 sum_3 = sum_3 + i * j;20 }21 }22 23 return sum_1 + sum_2 + sum_3;24 }这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度，然后把相加，再取一个量级最大的作为整段代码的复杂度。
第一段的时间复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行时间，跟 n 的规模无关。强调一下，即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。
那第二段代码和第三段代码的时间复杂度应该很容易分析出来是 O(n) 和 O(n^2)。
综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n^2)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
假设有一个嵌套的循环，我们把第一层循环叫T1,那么T1(n)=O(f(n))，第二层循环叫T2，那么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(n^2)，则 T1(n) * T2(n) = O(n^3)。在具体的代码上，我们可以把乘法法则看成是嵌套循环
如上面计算sum_3的代码段 两个循环为O(n^2)。
常见时间复杂度实例分析
O(1)
O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
1 const i = 8; 2 const j = 6; 3 const sum = i + j;
只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
O(logn)
对数阶时间复杂度非常常见，如
1 i=1;2 while (i <= n) {3 i = i * 2; 4 }根据说的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。实际上变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：
所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。
O(n)
O(n)级别有个非常显著的特征就，它会存在一个循环，且循环的次数是和n相关
1 function countSum (n) {2 let sum = 03 for (let i = 0; i < n; i++) {4 sum += i5 }6 }O(n^2)
O(n^2)级别的有双重循环
function countSum (n) { let sum = 0 for (let i = 0; i < n; i++) { sum += i for (let J = 0; J < n; i++) { // do some thing } }}不是所有的双重循环都是n^2
1 function countSum (n, m) {2 let sum = 03 for (let i = 0; i < n; i++) {4 sum += i5 for (let J = 0; J < m; i++) {6 // do some thing7 }8 }9 }这种是由两个数据规模n、m来决定的时间复杂度，所以是O(n * m)，关键还是要分析嵌套的循环跟外面那层循环的关系。
时间复杂度耗费时间从小到大依次排列
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
常见排序算法对应的时间复杂度
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏) | 时间复杂度（最好) | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 直接插入排序 | O(n2)O(n2) | O(n2)O(n2) | O(n)O(n) | O(1)O(1) | 稳定 | 简单 |
| 希尔排序 | O(nlog2n)O(nlog2n) | O(n2)O(n2) | O(n)O(n) | O(1)O(1) | 不稳定 | 较复杂 |
| 直接选择排序 | O(n2)O(n2) | O(n2)O(n2) | O(n2)O(n2) | O(1)O(1) | 不稳定 | 简单 |
| 堆排序 | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(1)O(1) | 不稳定 | 较复杂 |
| 冒泡排序 | O(n2)O(n2) | O(n2)O(n2) | O(n)O(n) | O(1)O(1) | 稳定 | 简单 |
| 快速排序 | O(nlog2n)O(nlog2n) | O(n2)O(n2) | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | 不稳定 | 较复杂 |
| 归并排序 | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(n)O(n) | 稳定 | 较复杂 |
| 基数排序 | O(d(n+r))O(d(n+r)) | O(d(n+r))O(d(n+r)) | O(d(n+r))O(d(n+r)) | O(n+r)O(n+r) | 稳定 | 较复杂 |
空间复杂度
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。同理，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系，空间复杂度分析跟时间复杂度类似。
1 function run (n) {2 let name = 'joel'3 let step= 24 const arr = []5 6 for (let i = 0; i < n; i++) {7 arr.push(i * step)8 }9 }再第4行代码我们初始化一个数组，再第7行代码对这个数组进行push 操作，这个循环是依赖外部的n，所以这个空间复杂度为 O(n)，我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )
原文转载：http://www.shaoqun.com/a/680736.html
skyee：https://www.ikjzd.com/w/290
拍拍网：https://www.ikjzd.com/w/2205
为什么需要复杂度分析 我们可以把代码跑一遍，然后通过一些工具来统计、监控就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？ 首先，肯定的说这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字，叫事后统计法。但是这种统计方法存在一定的局限性。1、测试结果依赖测试的环境以及数据规模的影响
拍拍购物：https://www.ikjzd.com/w/2205
洋老板：https://www.ikjzd.com/w/2779
亿恩网：https://www.ikjzd.com/w/1461
亚马逊英国站发布2018圣诞季&年度畅销品榜单：https://www.ikjzd.com/home/13459
过年休假7天，我的亚马逊店铺怎么不被同行超越：https://www.ikjzd.com/home/114575
揭秘！亚马逊卖家中心那些你不为所知的数据：https://www.ikjzd.com/home/20889
没有评论:
发表评论