算法与数据结构-复杂度分析

(文章目录)

  粗略地说，算法的执行效率是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”获得代码执行时间呢？

  这里有一个很简单的代码，请求 1,2,3...n 累加和。现在，我将带您一起估计代码的执行时间。

 int cal(int n) {   int sum = 0;   int i = 1;   for (; i <= n; ++i) {     sum = sum + i;   }   return sum; }

  从 CPU 从这个角度来看，这个代码的每一行都有类似的操作:读数据-操作-写数据。虽然每行代码对应 CPU 执行的数量和时间是不同的，但我们在这里只是粗略估计，所以我们可以假设每行代码执行的时间是相同的 unit_time。在此假设的基础上，该代码的总执行时间是多少？

  第 2、3 分别需要行代码 1 个 unit_time 执行时间，第 4、5 行都运行了 n 遍，所以需要 2n*unit_time 所以这个代码的总执行时间是 (2n+2)*unit_time。可以看出，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

  按照这个分析思路，我们再来看看这个代码。

 int cal(int n) {   int sum = 0;   int i = 1;   int j = 1;   for (; i <= n; ++i) {     j = 1;     for (; j <= n; ++j) {       sum = sum +  i * j;     }   } }

  我们仍然假设每个句子的执行时间是 unit_time。该代码的总执行时间 T(n) 是多少呢？

  第 2、3、4 每行都需要行代码 1 个 unit_time 执行时间，第 5、6 行代码循环执行 n 遍，需要 2n * unit_time 执行时间，第 7、8 行代码循环执行 N2次，所以需要 2n² * unit_time 执行时间。因此，整个代码的总执行时间 T(n) = (2n²+2n+3)*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)，第二个例子 T(n) = O(2n²+2n+3)。这就是大 O 时间复杂度表示法。大 O 事实上，时间复杂性并不意味着代码的真实执行时间，而是意味着代码执行时间随着数据规模的增长而变化。因此，它也被称为渐进时间复杂性（asymptotic time complexity），简称时间复杂度。

  当 n 当它很大的时候，你可以想象它 10000、1万。公式中的低阶、常量和系数并不影响增长趋势，因此可以忽略不计。如果我们使用它，我们只需要记录最大的量级 O 表示法表示刚才提到的两段代码的时间复杂性，可以记录为：T(n) = O(n)； T(n) = O(n²)。

  那么这个大 O 复杂性表示法与通过统计和监控获得算法执行的时间和内存的大小有什么区别？为什么要分析时间和空间的复杂性？这种分析方法能比我真正运行的数据更准确吗？

  首先，我可以肯定地说，你评估算法执行效率的方法是正确的。许多数据结构和算法书籍也给这种方法起了一个名字，称为事后统计法。

  但这种统计方法有很大的局限性。

• 1. 测试结果非常依赖于测试环境中硬件的差异，这将对测试结果产生很大的影响。例如，我们分别使用相同的代码 Intel Core i9 处理器和 Intel Core i3 不用说，i9处理器正在运行 处理器要比 i3 处理器执行速度要快得多。还有，比如原本在这台机器上。 a 代码执行的速度比 b 代码要快，当我们换到另一台机器时，可能会有相反的结果。
• 2. 测试结果受数据规模的影响很大。后来，我们将讨论排序算法。让我们以此为例。对于同一排序算法，当排序数据的有序性不同时，排序执行时间会有很大差异。在极端情况下，如果数据有序，则排序算法不需要进行任何操作，执行时间将非常短。

  此外，如果测试数据太小，测试结果可能无法真正反映算法的性能。例如，对于小规模的数据排序，插入排序可能比快速排序更快！ 因此，我们需要一种粗略估计算法执行效率的方法，而无需具体的测试数据进行测试。这种方法很大 O 复杂表示法。

  大 O 这种复杂性表示方法只表示一种变化趋势。我们通常忽略公式中的常数、低阶和系数，只需记录最大阶的量级即可。因此，当我们分析算法和代码的时间复杂性时，我们只关注循环执行次数最多的代码。这个核心代码执行次数 n 量级是分析代码整段的时间复杂性。

  为了方便你理解，我还是以前面的例子来解释。

 int cal(int n) {   int sum = 0;   int i = 1;   for (; i <= n; ++i) {     sum = sum + i;   }   return sum; }

  其中第 2、3 行代码是常量级的执行时间和 n 大小无关，所以对复杂性没有影响。循环执行次数最多的是第一个 4、5 行代码，所以这个代码要重点分析。正如我们前面所说，这两行代码已经执行了。 n 次，所以时间的总复杂度是 O(n)。

  我这里还有一个代码。你可以先试着分析一下，然后再往下看是否和我的分析思路一样。

int cal(int n) {   int sum_1 = 0;   int p = 1;   for (; p < 100; ++p) {     sum_1 = sum_1 + p;   }   int sum_2 = 0;   int q = 1;   for (; q < n; ++q) {     sum_2 = sum_2 + q;   }    int sum_3 = 0;   int i = 1;   int j = 1;   for (; i <= n; ++i) {     j = 1;      for (; j <= n; ++j) {       sum_3 = sum_3 +  i * j;     }   }    return sum_1 + sum_2 + sum_3; }

  这个代码分为三部分，分别是求 sum_1、sum_2、sum_3.我们可以分别分析每个部分的时间复杂性，然后把它们放在一起，然后把最大的量级作为整个代码的复杂性。

  第一段时间有多复杂？这个代码循环已经实现了 100 次，所以是一个常量的执行时间，跟随 n 规模无关。

  这里我想强调的是，即使这个代码循环 10000 次、100000 第二，只要是已知的数字，跟随 n 没关系，还是常量级的执行时间。当 n 当它无限大的时候，就可以忽略了。虽然它会对代码的执行时间产生很大的影响，但回到时间复杂性的概念，它代表了算法执行效率和数据规模增长的变化趋势，所以无论执行时间有多长，我们都可以忽略它。因为它本身对增长趋势没有影响。

  第二代码和第三代码的时间复杂性是多少？答案是 O(n) 和 O(n²)，你应该能很容易地分析出来，我就不啰嗦了。

  结合这三个代码的时间复杂性，我们选择了最大的量级。因此，整个代码的时间复杂性是 O(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)))

  这里还是给出一段代码，你先试着分析一下时间的复杂性，再往下看我给出的公式：

int cal(int n) {   int ret = 0;    int i = 1;   for (; i < n; ++i) {     ret = ret + f(i);   }  }   int f(int n) {  int sum = 0;  int i = 1;  for (; i < n; ++i) {    sum = sum + i;  }   return sum; }

  我们单独看 cal() 函数。假设 f() 这只是一个普通的操作，那是第一个 4～6 行的时间复杂度是，T1(n) = O(n)。但 f() 函数本身不是一个简单的操作，它的时间复杂性是 T2(n) = O(n)，所以，整个 cal() 函数的时间复杂度是，T(n) = T1(n) * T2(n) = O(n*n) = O(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))

  虽然代码差异很大，但常见的复杂度量级并不多。我总结了一下，这些复杂度量级是多少？它涵盖了你将来可以接触到的所有代码的复杂度量级。  对于刚刚列出的复杂度量级，我们大致可以分为多项式量级和非多项式量级两类。其中，只有两个非多项式量级：O(2ⁿ) 和 O(n!)。

  我们称时间复杂度为非多项式量级算法问题 NP（Non-Deterministic Polynomial，多项式)问题不确定。

  当数据规模 n 随着时间的增加，非多项量级算法的执行时间将急剧增加，解决问题的执行时间将无限增加。因此，非多项时间复杂性算法实际上是一种非常低效的算法。  因此，关于 NP 我不会谈论时间的复杂性。我们主要看几种常见的多项式时间复杂性。

  首先，你必须明确一个概念，O(1) 这只是常量级时间复杂性的一种表达方式，并不意味着只执行一行代码。例如，即使有这个代码 3 好吧，它的时间复杂性也是 O(1)，而不是 O(3)。

 int i = 8; int j = 6; int sum = i + j;

  只要代码的执行时间不随意 n 随着代码的增加和增加，我们都记得代码的时间复杂性 O(1)。换句话说，一般来说，只要算法中没有循环语句和递归语句，即使有成千上万行的代码，时间的复杂性也是Ο(1)。

  数阶时间的复杂性非常常见，也是最难分析的时间复杂性。让我举个例子来解释一下。

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

  根据我们之前提到的复杂性分析方法，第三行代码是循环执行次数最多的。因此，只要我们能计算出代码执行了多少次，我们就能知道整个代码的时间复杂性。

  从代码中可以看出，变量 i 的值从 1 开始取，乘以每个循环一次 2。当大于 n 循环结束了。还记得我们高中学到的等比数列吗？事实上，变量 i 值是等比数列。如果我一个一个列出来，应该是这样的:  所以，我们只需要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 我们认为我们应该在高中学习这个问题，所以我就不多说了。x=log2n，因此，这个代码的时间复杂性是 O(log2n)。

  事实上，不管是以 2 为底、以 3 最后，还是以 10 最后，我们可以把数阶的时间复杂度全部记录下来 O(logn)。为什么呢？

  我们知道对数可以相互转换，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是常量。基于我们之前的理论：我们正在采用大理论 O 当标记复杂性时，系数可以忽略，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在表达数阶时间复杂性的方法中，我们忽略了对数的“底部” O(logn)。

  如果你理解我之前说的话， O(logn)，那 O(nlogn) 很容易理解。还记得我们刚才提到的乘法规则吗？如果代码的时间复杂度是一段时间 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 算法时间复杂性也很常见。例如，合并排序和快速排序的时间复杂性是 O(nlogn)。

  让我们来谈谈时间的复杂性，它与以前不同。代码的复杂性取决于两个数据的规模。老规则，先看代码！

int cal(int m, int n) {  int sum_1 = 0;  int i = 1;  for (; i < m; ++i) {    sum_1 = sum_1 + i;  }  int sum_2 = 0;  int j = 1;  for (; j < n; ++j) {    sum_2 = sum_2 + j;  }  return sum_1 + sum_2;}

  从代码中可以看出，m 和 n 表示两个数据规模。我们不能提前评估它们。 m 和 n 因此，当我们表达复杂性时，我们不能简单地使用加法规则来省略其中一个。因此，上述代码的时间复杂性是 O(m+n)。

  在这种情况下，原来的加法规则是不正确的，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但乘法规则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

  前面，我们花了很长时间来谈论它 O 表示法和时间复杂度分析，理解上述内容，空间复杂度分析方法学习非常简单。

  正如我前面所说，时间复杂度的全称是渐进时间复杂度，表示算法执行时间与数据规模之间的增长关系。相比之下，空间复杂度的全称是渐进空间复杂度（asymptotic space complexity），存储空间与数据规模之间的增长关系表示算法。

  我还是以具体的例子给你解释一下。(这个代码有点“傻”，一般没人会这样写。我这样写只是为了方便向你解释。)

void print(int n) {  int i = 0;  int[] a = new int[n];  for (i; i <n; ++i) {    a[i] = i * i;  }  for (i = n-1; i >= 0; --i) {    print out a[i]  }}

  就像时间复杂度分析一样，我们可以看到，第一， 2 在行代码中，我们申请了一个空间存储变量 i，但它是常量阶，与数据规模相匹配 n 没关系，可以忽略。第一 3 银行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码没有占用更多的空间，所以整个代码的空间复杂性是 O(n)。

  我们常见的空间复杂性是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这种对数阶的复杂性通常不使用。此外，空间复杂性分析比时间复杂性分析简单得多。因此，掌握我刚才说的空间复杂性就足够了。