Big O вопрос

Question

Если у меня есть следующий код:

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

и производительность время в Dosomething(object) метода является O (журнал N), является общая производительность IterateArray O (п) или O (п журнал п) ?

Спасибо.

Answer 1

Было бы O (п § п)

Вы делаете в O (журнал п) операцию производительности п раз, а умножение выполняется с Big O, поэтому O (N) * O (журнал N) = O (n log n)

Важно отметить, что между m и n действительно не должно быть различий, если вы смотрите на два массива разных размеров. Причина в том, что m и n - оба константы, и они асимптотически эквивалентны, если вы должны были рассчитать их темпы роста.

Answer 2

O (п § п)

Подумайте об этом - вы выполняете журнал н операцию п раз.

Answer 3

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

веселит

Answer 4

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

Answer 5

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

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

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