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)的整体性能？

Answer 1

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

答案很长:把它写成O(n log m)会更准确.

除非DoSomething真的依赖于整个阵列,否则看起来它在单个元素上运行.所以我们用"m"分别区分它.

Answer 2

那将是O(n log n)

你正在执行O(log n)性能操作n次,并且乘法与Big O一致,所以O(n)*O(log n)= O(n log n)

重要的是要注意,如果您正在查看两个不同大小的数组,那么m和n之间确实不需要有任何区别.原因是m和n都是常数,如果要绘制它们的增长率,它们是渐近等价的.

Answer 3

O(n log n)

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