用循环表示的对数复杂度？

Question

据我所知,线性复杂度可以表示为简单循环,二次复杂度可以表示为嵌套循环.如何表示立方和对数复杂度？

谢谢!

Answer 1

简单的循环可以具有对数复杂度,例如

for (i = 1; i <= N; i *= 2)
    ...

正如其他人已经回答的那样,三重嵌套循环将具有立方复杂性.

Answer 2

由于三次为O（n ^ 3），因此它将是三个嵌套循环。

对数不是那么简单，通常需要递归关系。例如，MergeSort为O（n * log（n）），因为它形成了高度为log（n）的递归树，并且每个级别都需要O（n）合并操作。