N对数(N)或N澄清

Question

执行O(log N)算法N次会给出O(N log(N))吗？还是O(N)？

例如，在自平衡树中插入N个元素。

int i = 0;
while (i++ < N) {
    insert(itemsToInsert[i]);
}

Answer 1

它绝对是O(N log(N))。它也可能是O(N)，如果您可以显示调用的顺序，作为一个整体，增长足够慢(因为有些调用是O(log )，而其他调用足够快，例如O(1)，使总数下降)。

记住: O( f )意味着算法并不比f慢，但是它可以更快(即使只是在某些情况下)。

Answer 2

N乘以O(log(N))导致O(N log(N))。

Answer 3

大-O符号说明了该算法的渐近行为.每个附加步骤的代价是O(log N)，我们知道对于O(N)算法，每个附加步骤的代价是O(1)，并且渐近地代价函数界是一条直线。

因此，O(N)太低了；O(N log N)似乎是对的。