Большой 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), является ли общая производительность IterateArray O (n) или O (n log n)?

Answer 1

Короткий и несколько неправильный ответ: O (n log n).

Длинный ответ: правильнее было бы написать его как O (n log m ).

Если DoSomething действительно НЕ зависит от всего массива, похоже, что он работает на одном элементе. Таким образом, мы различаем это отдельно, используя «м».

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 раз.

Answer 4

Для каждого из ваших m объектов, если производительность DoSomething () равна O (log n), то общая производительность по всем вашим m объектам будет равна O (m log n).

Answer 5

Поскольку цикл for повторяется n (скажем, длина массива n) раз, и в каждой итерации выполняется «Dosomething», общая производительность будет O (n logn).

ура