algorithm - 时间复杂度算法

Question

我有一个算法可以完成 O(n) 工作，摆脱输入的恒定分数 1/k (k > 2)，并在剩余的内容上递归调用自身。该算法可以用 T(n) = T( ( (k-1)/k)*n)+O(n) 来描述。如何计算 T(n) 的封闭形式。

Answer 1

可以直接展开： T(n) = T(((k - 1)/k)^2 * n) + O(((k - 1)/k) * n) + O(n) 以此类推

请注意，n * ((k-1)/k) 是 n / (k / (k - 1))，这意味着分母 > 1。

因此，它是一个几何级数，收敛于和 n / ( 1 - (k - 1)/k) = n * k。

因此 T(n) = O(n*k) 如果 k 是常数，则为 O(n)。

Answer 2

您可能想了解 Master Theorem，这是分析此类问题的便捷方法：http ://en.wikipedia.org/wiki/Master_theorem

您的算法将属于情况 3，与外部工作相比，递归工作可以忽略不计。