对数复杂度用循环表示

Question

据我所知，线性复杂度可以表示为简单循环，二次复杂度可以表示为嵌套循环。如何表示三次和对数复杂度?

谢谢!

Answer 1

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

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

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

Answer 2

由于立方是O(n^3)，它将是三个嵌套循环。

对数不是那么简单，通常需要递归关系。例如，MergeSort是O(n*log(n))，因为它形成了一个高度为log(n)的递归树，每一层都需要O(n)次归并操作。

Answer 3

• 立方-三个嵌套循环
• 对数-在每个循环周期中，您将输入数据集分成部分(或以某种方式使其更小)，并在下一个循环过程中缩短数据集，因此基本上复杂性不会随着输入数据集的增长而显着增长。例如，看看BinarySearch算法或任何其他分而治之算法。

Answer 4

立方复杂度-三个嵌套循环:

foreach
   foreach
      foreach
      // actions
      end
   end
end

对数复杂度示例-二进制搜索。

Answer 5

0 (n^3)可以用3个嵌套循环表示。

O(log n)由一个循环表示，每次迭代，需要处理的数据量减少一半。