算法的时间复杂度分析题笔记

为了加强自己在算法上的能力，我陆陆续续从网上整理了一些计算程序时间复杂度的习题（为了可读性，大部分代码我做了一些修改），然后附上了求解过程。

题1

原题来源：未知 

void func(int n) {
  int i = 1;

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

循环结束条件是 i ≤ n，关键语句是 i = i * 2。每循环一次，i 就更趋进于 n，假设执行时间为 T(n)，所以要求的是 2T(n) ≤ n，即 T(n) ≤ log2n，所以复杂度为：\(O(log_{2}n)\)。

题2

原题来源：未知 

void func(int n){
  int i = 0;

  while(i * i * i <= n)
    i++;
}

循环结束条件是 i × i × i ≤ n，即 i3 ≤ n。循环的基本运算是 i++，假设运行时间为 T(n)，则 T(n)3 ≤ n，即 \(T(n) \le \sqrt[3]{n}\)，因此复杂度为 \(O(\sqrt[3]{n})\)。

题3

原题来源：未知 

int func(int n){
  if (n <= 1)
    return 1;

  return n * func(n - 1);
}

函数结束条件是 n = 1，这个函数共执行了 n × (n - 1) × … × 1 次操作，因此复杂度为 \(O(n)\)。

题4

原题来源：2011 年计算机联考真题 

void func(int n) {
  x = 2;

  while( x < n / 2)
    x = 2 * x;
}

x = 2 * x 是关键语句，循环每执行一次，x 就增加 2 倍。可以观察下规律： 

如果执行 1 次，x = 4
如果执行 2 次，x = 8
如果执行 3 次，x = 16

假设程序要执行 t 次，那么 t = 2t+1。因为函数结束条件是 \(x \ge \frac{n}{2}\)，所以 \(2^{t+1} = \frac{n}{2}\) 函数才能结束，即 \(t = log_{2}\frac{n}{2} - 1 = log_{2}{n} - log_{2}{2}\)，由此得出复杂度是 \(O(\log_{2}{n})\)。

题5

原题来源：京东面试题 

void recursive(int n, int m, int o) {
  if (n <= 0) {
    printf("%d, %d\n", m, o);
  } else {
    recursive(n - 1, m + 1, o);
    recursive(n - 1, m, o + 1);
  }
}

函数结束条件是 n ≥ 0，后面两次递归调用自身，又因为参数 m 和 o 没有参与判断，所以运行时间可简化为 T(n) = T(n - 1) + T(n - 1)，即 T(n) = 2 × T(n - 1)，这是一个递归式：

所以复杂度为 \(O(2 ^ {n})\)。

题6

原题来源：未知 

void func(int n) {
  for (int i = 1, s = 0; i <= n; ++i) {
    int t = 1;

    for (int j = 1; j <= i; ++j)
      t = t * j;

    s = s + t;
  }
}

第一层循环的结束条件是 i ≤ n，共执行 n 次。

第二层循环的结束条件是 j ≤ i。

当 i = 1，循环执行 1 次，当 i = 2，循环执行了 2 次。

所以总执行了 n + (n - 1) + (n - 2) … + 1 次，即：\(\frac{n(n + 1)}{2} = \frac{n^{2}}{2} + \frac{n}{2}\)，然后只保留高阶项 \(\frac{n^{2}}{2}\)，再变换成 \(n^{2} \times \frac{1}{2}\)，去掉常数 \(\frac{1}{2}\) 后，求出的复杂度为 \(O(n^{2})\)。