该算法的复杂度公式

Question

我有这个算法（黄金比例）：

public static float golden(int n){

float res;

if(n == 0) {
  res = 1;
} else {
  res = (float) (1.0 + (1.0 / golden(n-1)));
}
return res;

}

我想T(n)公式是T(n-1)。我可以按照这个公式得到复杂性。

T(n) = aT(n - b) + c^n p(n)

还有这个：

p(n) 和 c 是多少？

Answer 1

对于每个 n > 0，对 golden(n) 的调用会导致恒定数量的算术运算和一次递归调用，因此您可以将递归写为时间复杂度函数 T(n) as

T(n) = T(n-1) + k, n>0

其中 k 是每次调用中的操作数。这是顺序搜索的递归关系。

现在你可以应用你在问题中提到的公式了。回想一下，公式中的 d 是多项式 p(n) 的次数。这里

a = 1, c = 1, b = 1, p(n) = k,

因此 d = 0，现在应用你的公式你会得到 a=c^b，因此第二种情况适用，所以

T(n) = Theta(n^{d+1}c^n) = Theta(n).

这给出了最终答案T(n) = Theta(n)。