算法复杂度小记

Tags:

本文主要书写了本人对于算法复杂度的一些理解，并辅以一些例子进行说明

算法复杂度的概念

从一个简单的例子入手

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

  return sum
}

cal 是一个简单的求和函数, 我们将它的执行时间定义为 \( T(n) \) 。从 CPU 的角度来看，每一行代码都执行着类似的操作 读数据 - 运算 - 写数据 。

尽管每行代码编译出来的汇编代码都是不同的(汇编指令的个数也不同)，执行时间也都不一样。但我们这里只是粗略估计，为了简单起见，我们将每一行的代码的执行时间都定义为 unit_time。

第 2, 3 行只执行需要一个 unit_time， 第4, 5行需要执行 N 个 unit_time, 可以得到

$$ T(n) = unit\_time * (1 + 1 + n + n) = unit\_time * (2n + 2) $$

上述分析中，我们忽略了调用函数时入参和返回参数所需的时间

定义 \( f(n) = 2n+2 \)，由于 unit_time 始终都是一个正数，我们可以得出 cal 函数的执行时间 \( T(n) \) 和每行代码的执行次数 \( f(n) \) 成正比

以上关系我们可以用 字母 O 来表示:

  • \( T(n) = O(f(n)) ，即代码的执行时间 T(n) 和 某个函数 f(n) 成正比。\)

但是准确计算某个函数共有多少行代码需要执行，这也是一个困难的工作，我们可以将 O 的定义进一步精确。

  • \( T(n) = O(f(n)) \)，代码的执行时间随着数据规模(n)增长的 增长趋势。所以，O 也叫做渐进时间复杂度( asymptotic time complexity)，简称时间复杂度。

复杂度的计算理念

  • 我们不对某个算法进行精确的分析，只需要初略地知道它的 增长趋势 就可以了。
  • 平常我们分析算法复杂度的时候，通常有分析最坏情况和平均情况两种选项，由于最坏情况易于分析，所以我们一般分析算法复杂度的最坏情况。

复杂度的渐进表示法

  • 上界

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

上述式子表示当N足够大的时候，f(n)函数是T(n)的上界。

  • 下界

$$ T(n) = \Omega(h(n)) $$

上述式子表示当N足够大的时候，h(n)函数是T(n)的下界。

  • 上界和下界同时成立

$$ T(n) = \Theta(g(n)) $$

上述式子表示当N足够大的时候，g(n)函数同时是T(n)的上界和下界。

  • 在上面三个式子中，T(n)表示的都是某个算法的时间复杂度，它们也可以应用在算法的空间复杂度S(n)上。
  • 一个算法的上界和下界函数可能有无穷多个，为了和现实的情况更贴合，我们在使用上述式子表示算法的复杂度的时候，通常使用 最小的上界 和 最大的下界 。

复杂度的增长趋势比较

$$ O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) $$

上面的复杂度量级，我们可以粗略地分成两类， 多项式量级和非多项式量级。其中，非多项式量级只有两个：指数阶 \( O(2^n) \) 和 阶乘阶 \( O(n!) \)

我们把时间复杂度为非多项式量级的算法问题叫做 NP (Non-Deterministic Polynomial，非确定多项式) 问题。

算法复杂度的分析规则

加法法则

多个复杂度相加，取量级最大的时间复杂度，这个规则用公式表示为:

$$ T_1(n) = O(f_1(n)), T_2(n) = O(f_2(n)) $$

$$ T_1(n) + T_2(n) = max(O(f_1(n)), O(f_2(n))) $$

由于我们分析算法复杂度的时候主要是分析它的 增长趋势 ，所以我们只需要分析算法复杂度的 某个主要趋势 即可。

有时间复杂度计算公式，

$$ T(n) = O(C_1 * n^2 + C_2 * n) $$

\( 在N进行增长的时候，n^2 对于 T(n) 增长的影响是远远大于 n 的，所以我们就可以忽略掉 n ，认为 T(n) = O(C_1 * n^2) \)， 常数项量级也可以忽略掉，最终为

$$ T(n) = O(n^2) $$

  • 即当 n 很大的时候，\( n^2 为 T(n) 的上界函数。\)
  • 即随着 n 的增长，某个算法所用的时间 \( T(n) \) 的 增长趋势 是 \( n^2 \)

\( 总结可得，当 T(n) 是关于n的k阶多项式的时候， T(n) = O(n^k) \)

分析代码时，可以得出:

一个if-else的复杂度 = max(条件判断式的复杂度，if分支的复杂度，else分支的复杂度)

忽略常数项

当我们谈论时间复杂度 \( \log N \) 的时候，我们并没有说明 \( \log N \) 是以2，以10还是以e为底的。

这是因为当N很大的时候，\( \log_{2} N 和 \log_{10} N \) 它们之间相差了常数倍。

$$ log_2N = log_{10}N * log_2 10 $$

其中 \( \log_2 10 \) 是一个常数

\( \log N \)的增长趋势是大于常数的增长趋势的，所以我们可以忽略掉底数的差异，直接以\( \log N \) 代指一种增长趋势。

乘法法则

嵌套代码的复杂度等一嵌套内外代码复杂度的乘积，这个规则用公式表示为

$$ T_1(n) = O(f_1(n)), T_2(n) = O(f_2(n)) $$

$$ T_1(n) * T_2(n) = O(f_1(n) * f_2(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 函数除了5行，其他地方的时间复杂度是 \( O(n) \), f 函数的时间复杂度是 \( O(n) \) 整个 cal 函数的时间复杂度就是

$$T(n) = T1(n) * T2(n) = O(n*n) = O(n^2)$$

分析代码时，可得:

一个for循环的复杂度 = 循环体的复杂度 * 循环次数

空间复杂度

上文说到, 时间复杂度的全称是 渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

类比一下，空间复杂度的全称就是 渐进空间复杂度 (asymptotic space complexity)，表示算法的存储空间和数据规模之间的增长关系。

先看一段简单的代码

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

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

上述代码中，第二行申请了一个固定大小的内存空间，第三行申请了一个大小为 n 的 int 类型的数组，其他行都没有申请内存空间，我们可以忽略。

所以整段代码的空间复杂度就是 \( O(n) \)

我们常见的空间复杂度就是 \( O(1), O(n), O(n^2) \)，像 \( O(logn), O(nlogn) \) 这样的对数阶复杂度平时都用不到。

参考资料

2017年09月08日 / 00:24