performance - 大 O : is the overall performance of `IterateArray` O(n) or O(n log n)?

Question

如果我有以下代码:

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

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

Answer 1

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

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

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