【先导篇】如何衡量算法的性能

[azl397985856]

给定代码，分析时间复杂度是学习算法最核心的技能之一，务必掌握。 请分析下面代码的时间空间复杂度，并解释原因。

下面的代码打印了所有从 0 到 n 的斐波那契数列。时间复杂度是多少？

   void allFib(int n) {
          for (int i = 0; i < n; i++) {
            System.out.println(i + ": " + fib(i));
          }
        }

        int fib(int n) {
          if (n <= 0) return 0;
          else if (n == 1) return 1;
            return fib(n - 1) + fib(n - 2);
        }

[coderXiaowq]

我的思路:因为有n个数,要分解到n=1,所以要分解n-1次;第1次分解需要计算2次,第2次分解需要计算4次,...,第n-1次分解需要2^(n-1)次,所以总共需要计算2^n次,时间复杂度O(2^n)

[Alexzhang-Mini]

代码中的allFib()函数对每次变量都调用了fib()函数，fib()是一个递归调用函数，在这个函数中，通过fib(n)的计算，需要计算fib(n-1)和fib(n-2)。所以这个递归调用的树形结构就像一颗二叉树，每个节点会产生两个子节点。所以时间复杂度应该是O(2^n)。在allFib()函数中，从0-n，每次变量i都调用了一次fib(i)。这意味着会有fib(0)，fib(1)...fib(n) 。所以，总时间复杂度应该是fib(0)+fib(1)+…+fib(n) 的时间复杂度。由于斐波那契函数的时间复杂度为 O(2^n)，所以整个函数的时间复杂度应该是 O(2^0) + O(2^1) + O(2^2) +...+O(2^n)。在大 O 记法中，只考虑项数中最大的项，因此总的时间复杂度是 O(2^n)。然后这个代码的空间复杂度也是指数级的，因为递归调用会在调用栈上产生大量的重复调用，占用大量内存空间。所以空间复杂度与时间复杂度相同，都是 O(2^n)。

[atom-set]

思路

fib(n) 的递归求解过程：

fib(n) = fib(n-1) + fib(n-2) fib(n-1) = fib(n-2) + fib(n-3) fib(n-1) = fib(n-2) + fib(n-3) ... f(3) = f(2) + f(1) f(2) = f(1) + f(0) f(1) = 1

递归求解过程类似构建一颗平衡二叉树，并遍历每一个节点。

高度为 n 的平衡二叉树节点个数是 2^n-1。即时间复杂度是 2^n

递归求解过程中使用了栈，不考虑额外空间的话，栈的长度为 n，即空间复杂度是 2^n

复杂度分析

• 时间复杂度：O(2^N)，其中 N 为数据规模
• 空间复杂度：O(N)，其中 N 为数据规模

[hillsonziqiu]

思路

斐波那契数列算法： f(n) = f(n - 1) + f(n - 2);
fib的时间复杂度为 O(2^n); allFib的时间复杂度是 O(n fib(n)) == O(n2^n) ;

在每一层递归中需要的存储的空间是递归深度。故空间复杂度就是 O(n);

结论

• 时间复杂度 O(2^n);
• 空间复杂度 O(n)；

[Martina001]

fib内部需要从2处理到n，共n-1次，每次 f(n) = f(n - 1) + f(n - 2) 计算两个递归，总共2的n-1次方 allfib函数遍历n次 总共2的n次方时间复杂度

空间复杂度只有递归用到了栈，深度为n 故空间复杂度为n

[jinzhepro]

思路

波那契数列的递归树是一个二叉树，其中每个节点都会分裂成两个子节点，直到达到叶子节点（即 fib(0) 或 fib(1)），节点总数大约是 2^n，因此函数调用的总数也是 2^n。

结论

对于allFib函数而言，时间复杂度为O(n * 2^n)，取最大项为O(2^n)，空间负复杂度为O(n)

[CathyShang]

思路

斐波那契数列打印实则一个平衡二叉树， fib(2) 操作数为 3 fib(3) 操作数为 5 fib(4) 操作数为 9 fib(n) 操作数为 $2^{n-1}-1$ 所以 $O(2^{n})$

[xil324]

[hillsonziqiu]

思路

斐波那契数列算法： f(n) = f(n - 1) + f(n - 2); fib的时间复杂度为 O(2^n); allFib的时间复杂度是 O(n fib(n)) == O(n2^n) ;

在每一层递归中需要的存储的空间是递归深度。故空间复杂度就是 O(n);

结论

• 时间复杂度 O(2^n);
• 空间复杂度 O(n)；

纠错

allFib: O(2^0+2^1+...+2^(n-1)) 等比数列求和 O((1-2^n) / (1-2)) = O(2^n - 1) => O(2^n); 故复杂度allFib复杂度为O(2^n);

[borderGong]

答案

• O(n) * O(2的n-1次方)

思路

• fib的为递归函数，递归函数有两个分支所以时间复杂度为O(n的m次方) n为递归的分支数，m为递归的深度
• allFib只看循环的时间复杂度为O(n)
• 合一起调用的复杂度为O(n) * O(2的n-1次方)