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

我知道Fibonacci算法的规则递归函数是O（2^n），因为它为每个后续调用调用自己两次，使其成本加倍。但是，在添加我所描述的优化（对序列的解决方案哈希表）之后，如何确定它有多少可以降低复杂性？如何确定包含优化的递归算法的大O？

例如：

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)); 
    } 
}

来源

2017-10-17 Remixt

1.“我知道斐波纳契算法的正则递归函数是O（n^2）” - 不是，它是O（2^n）。 2.你永远不会填充'数字'。 3.一旦你实现了一个真正的记忆，你将只计算一次每个数字，所以'n'的运行时间将是O（n） – alfasin

我犯了一个错误，对不起 – Remixt

它也不是2^n，但phi^n，其中phi =（sqrt（5）+1）/ 2 = 1.618 ...是黄金比例。斐波纳契（30）需要大约200万步来计算天真，而不是10亿。（从技术上讲，它是O（2^n），但只是在同样的意义上，它是O（2^2^n）：大O是一个上界。） – Charles

你的算法是O（n）。你已经实施的是所谓的memoization。这意味着当两个（或一般多个）子问题部分重叠时（例如F(5) = F(4) + F(3)）突破问题时，两者将需要计算F（2）以使它们重叠），当计算一个值时，它将被存储，以便下一步所需时间已经计算完毕。

这意味着，为了计算你会递归计算所有F(i) ,i<n如果某些F(i)是不止一次需要的时候将被计算一次，并且会在O(1)可用（由于Ø哈希表）。所以总体会O(n)。

这与动态算法版本非常相似（不同之处在于，您不需要构建解决方案，例如F（0），F（1），F（2）... F（n）跟踪你的计算（记忆））。虽然我没有检查过你是否记忆算法有任何bug ...只是解释memoization算法的概念和复杂性。

来源

2017-10-17 18:43:05 coder

正如评论指出的那样，这个功能的复杂性是西塔（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)。这完成了证明。

溶液的散列表（有时称为备忘录，从那里memoization的）防止从Fibonacci(k)被调用超过每k一次。由于Fibonacci(n)仅取决于Fibonacci(0)，Fibonacci(1)，...，Fibonacci(n-1)，并且由于哈希表和检查防止这些被调用的次数超过一次，所以每次只调用一次，并且由于每个给定的工作量都是恒定的n，总工作量为O(n)。再现关系现在很难考虑（我们有副作用和需要条件），所以我必须利用这种“诡计”的论点。不幸的是，大多数证明都需要某种“窍门”，归纳是一种例外。

来源

2017-10-17 20:56:17 Patrick87

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

回答

相关问题