时间复杂度

Question

我有一些算法，我想找出它的时间复杂度。我想出了一些答案，但我不确定他们是对还是错。有人能帮帮我吗？

public static int f4(int N){
   if (N == 0) return 0;
   return f4(N/2) + f1(N) + f4(N/2);
} // f1 had a time complexity of O(n)

1)我相信这个是O(n)。

public static find f6(int N){
   if (N == 0) return 1;
   return f6(N-1) + f6(N-1);
}

2)我相信这是O(n!)或O(n)。

Answer 1

第一个问题的分析

master theorem指出，给定表单f(n) = a*f(n/b) + O(n^k)的重复出现，可能会导致三种类型的复杂性：

如果log_{b}(a) < k

• The时间复杂度为

• ，则时间复杂度为O(n^k)；如果log_{b}(a) < k

• The时间复杂度为log_{b}(a) == k

• The，则时间复杂度为O(n^k)；如果时间复杂度为O(n^k log n)，则时间复杂度为O(n^(log_{b}(a))

第一次递归采用以下形式：

f4(N) = 2f4(N/2) + O(n) = 2f4(N/2) + O(n^1)

这显然属于第二种情况，即log_{2}(2) == 1。因此，正确的答案是O(n log n)。

您的第一个问题具有polylogarithmic时间复杂性。

第二个问题的分析

递归的形式为

f6(N) = 2f6(N - 1)

您可以按如下方式展开：

f6(N) = (2^k)f6(N - k)

只需将该关系应用于f6(N-1)、f6(N-2)等。

由于f6(0)立即返回，即只需一个步骤即可返回，因此完整的运行时复杂度为

f6(N) = 2^N 

只需插入k == N即可。

因此，第二个问题具有指数时间复杂度。

Answer 2

我认为最好像调用方法那样递归地解决这个问题。对于函数f6：

T(n) = 2T(n-1) + c      = > T(n-1) = 2T(n-2) + c
Then : T(n) = 2(2T(n-2)) + c) + c 
T(n) = 4T(n-2) + 2c + c      => T(n-2) = 2T(n-3) + c
T(n) = 4(2(T(n-3) + c) + 2c + c 
T(n) = 8T(n-3) + 4c + 2c + c
.
.
.
T(n) = 2^i T(n - i) + 2^(i-1)c + 2^(i-2)c + ... + (2^0)c
When i asymptotically goes to n , that is : i => n , then : 
T(n) = 2^n T(n-n) + 2^(n-1)c + 2^(n-2)c + ... + (2^0)c
T(n) = O(2^n)

Answer 3

Akshat的答案是详细的。

https://stackoverflow.com/a/43880977/6866309

如果第二个函数内部有一个循环，那么它将变成O(n!)。

类似下面的例子是O(n!)。

f6(int N){
   if (N == 0) return 1;

   for(int i=0; i<N; i++) {
      f6(N-1) + f6(N-1);
   }
}