如何确定给定递归函数的 运行 时间 T(n)？

Question

如何确定下一个函数的T(n)的递推公式？

if(N == 0)
  return 1;

s = 0;

x = function(N/3);

for(i = 1; i <= N; i++){
  s += x;
}

return s;

Answer 1

您可以确定递归调用 x = function(N/3)，其复杂度为 T(n/3)。以下是 N 加法，因此要考虑 N 操作。

因此这个函数复杂度的递推关系是

T(n) = T(n/3) + n

因此

T(n) = O(n.log3(n))

Answer 2

您可以使用大师定理：

T(n) = a*T(n/b) + C * n^k（a,b,C > 0，k 在 N 中）。

情况 1：a < b^k --> T(n) 在 Θ (n^k)

情况 2：a = b^k --> T(n) 在 Θ (n^k * log (n))

情况 3：a > b^k --> T(n) 在 Θ (n^logb a)

在你的情况下 T(n) = 1 * T(n/3) + С * n^1.

a = 1, b = 3, k = 1 --> T(n) 在 Θ (n) 中。