performance - Big O：`IterateArray`的整体性能是O(n)还是O(n log n)？

Question

如果我有以下代码：

IterateArray(object[] array)
{
    for(int i=0; i<array.length; i++)
    {
        Dosomething(array[i]);
    }
}

并且Dosomething(object)方法的时间性能是O(log n)，整体性能是IterateArrayO(n)还是O(n log n)？

score 14 · Accepted Answer

简短且有些错误的答案是 O(n log n)。

长答案：将其写为 O(n log m )会更准确。

除非 DoSomething 真的依赖于整个数组，否则它看起来像是在单个元素上运行。所以我们分别用“m”来区分。

score 12 · Accepted Answer

这将是 O(n log n)

您正在执行 n 次 O(log n) 性能操作，并且乘法与 Big O 保持一致，因此 O(n) * O(log n) = O(n log n)

重要的是要注意，如果您正在查看两个不同大小的数组，则 m 和 n 之间实际上不需要任何区别。原因是 m 和 n 都是常数，如果要绘制它们的增长率，它们是渐近等效的。

score 10 · Accepted Answer

10

O(n log n)

想想看 - 你正在执行 n 次 log n 操作。

于 2009-07-09T19:51:45.387 回答

score 4 · Accepted Answer

对于 m 个对象中的每一个，如果 DoSomething() 的性能为 O(log n)，那么所有 m 个对象的总性能将为 O(m log n)。

score 1 · Accepted Answer

由于“for”循环迭代 n 次（例如数组长度为 n）次，并且在每次迭代中执行“Dosomething”，整体性能将是 O(n logn)。

干杯

5 回答 5