计算时间复杂度[重复]

Question

这个问题在这里已有答案：

• Big O, how do you calculate/approximate it? 23回答

计算等式的步数和时间复杂度：

T（n）= 2T（n / 4）+ 5其中n> 1，T（1）= 1

什么是大O符号？

Answer 1

你的第二步不正确。您必须替换T（n / 4）项，而不只是添加到等式的末尾。那样你得到：

T（n）= 2T（n / 4）+ 5

= 2（2T（n / 16）+5）+5 =2²T（n / 16）+（2¹+ 1）* 5

=2²（2T（n / 64）+5）+（2¹+ 1）* 5 =2³T（n / 64）+（2³+ 1）* 5

=2³（2T（n / 256）+5）+（2³+ 1）* 5 =2⁴T（n / 256）+（2⁶+ 1）* 5