我有一种算法可以执行O（n）的工作，消除输入的恒定分数1 / k（k> 2），然后对剩余的内容进行递归调用。可以通过T（n）= T（（（k-1）/ k）* n）+ O（n）来描述该算法。如何计算T（n）的封闭形式。
您可以直接展开它：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）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句