如何确定包含优化的递归算法的大 O?

Question

我知道斐波那契算法的常规递归函数是 O(2^n)，因为它在每次后续调用中调用自己两次，使其成本翻倍。但是，在添加了我所看到的描述为优化(序列解决方案的哈希表)之后，您如何确定它降低了多少复杂性(如果有的话)？

例如：

import java.util.*;
public class Solution {
static Hashtable<Integer, Integer> numbers = new Hashtable<Integer, Integer>();
public static int fibonacci(int n) {
if(n == 0 || n == 1){
return n;
}else if(numbers.containsKey(n)){
return numbers.get(n);
}else {
int result = fibonacci(n-1) + fibonacci(n-2);
numbers.put(n, result);
return result;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
System.out.println(fibonacci(n));
}
}

Answer 1

你的算法是 O(n)。你已经实现的就是所谓的记忆。这真正意味着，当将问题分解为两个(或一般更多)部分重叠的子问题(例如F(5) = F(4) + F(3))时，两者都需要计算F(2)以便它们重叠)，当计算一个值时，它被存储起来，所以下次需要它已经被计算出来了。

这意味着为了计算F(n)您将递归计算所有F(i) ,i<n，如果需要多次F(i)，则仅计算一次，并且将在O(1)中可用(由于哈希表)。所以总体上会O(n).

这与动态算法版本非常相似(但差异很小，而不是构建解决方案，例如 F(0)、F(1)、F(2) ......F(n)你向后做，跟踪你计算的内容(记忆)。虽然我没有检查你的记忆算法是否有任何错误......只是解释记忆算法的概念和复杂性。

Answer 2

正如注释中指出的，这个函数的复杂性是 Theta(2^n)：

Fibonacci(n) {
if (n < 0) return 0;
if (n < 2) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}

我们可以通过归纳来证明这一点。基本情况：对于n = 0和n = 1，0.5 * 2^n <= Fibonacci(n) = 1 <= 2 * 2^n。归纳假设：假设这适用于n，包括k。归纳步骤：显示0.5 * 2^(k+1) <= Fibonacci(k+1) <= 2 * 2^(k+1)。替换，我们得到0.5 * 2^(k+1) = 2*2^(k-1) <= 2*Fibonacci(k-1) <= Fibonacci(k) + Fibonacci(k-1) <= 2*Fibonacci(k) <= 2 * 2^k <= 2 * 2^(k+1).这样就完成了证明。

解决方案的哈希表(有时称为备忘录，因此记忆)可防止Fibonacci(k)在每次k多次调用。由于Fibonacci(n)只依赖于Fibonacci(0)、Fibonacci(1)、...、Fibonacci(n-1)，并且由于哈希表和检查防止其中任何一个被多次调用，所以每个都只被调用一次，并且由于每个对任何给定n做恒定的工作量，所以总工作量是O(n)。递归关系现在更难考虑(我们有副作用，需要条件)，所以我必须利用这种"技巧"论点。不幸的是，大多数证明都需要某种"技巧"，归纳法是一个例外。