0

我正在努力从代码中计算出 big-o 符号。

我了解基本步骤，即

for (int i = 0; i < n; i++)将是O(n)

然后

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)

将是O(n 2 )

我正在努力理解在哪里或如何计算对数值。

IE

将 ：

for (int i = 0; i < n * 2; i++)为O(log n)或O(n log n)或O(log 2n)等

有人可以以代码形式演示一个示例以及符号是如何形成的。

我已经研究并不断获得涉及排序和列表被切碎等的示例，这在形式上是有意义的，但我似乎不知道如何将其应用于上述代码。

我对整个编码和大符号表示法是新手。

我熟悉对象、类、循环、函数、结构等。我正忙于学习 c++，因为它是我课程的一部分。我的教科书没有很好地或几乎没有解释对数 big-o 计算。

4

1 回答 1

1

可以将代码表示为递归关系：

T(n) = T(n-1) + 2 * c, where c = the inner part of the code,

我们会做2 * n几次。

为我们提供解决方案，例如： T(n) = 2 c n + c_1, where c_1 a constant

由于2 * c是一个常数，而第二项，也是一个常数下降，我们可以写成：

O(n)

于 2017-03-28T21:41:48.907 回答