我正在查看一份算法 PPT，其中有一次给出 f(n) = b*n + f((n-1) 的复杂度为 O(n^2)。 我的分析是:f(n) = b*n + f(n-1)
=b*n + b*(n-1) + b*(n-2)...
= c * n
其中C是常数。这使得复杂度达到 O(n)。我很确定我在某个地方出错了。有人能解释一下吗？
最佳答案
=b*n + b*(n-1) + b*(n-2)...
此等式中将是“n”次求和，因此您不能将其替换为 C，它将是“n”中的“n”次求和，因此为 n^2
关于time-complexity - f(n) 的复杂度 = b*n+f(n-1)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21129603/