Время Вычислительная сложность?

У меня есть этот код сортировки, ниже которого находится сортировка пузырьков, но я думаю, что этот код не является точно O (N ^ 2). Мне было интересно, что будет сложной вычислительной сложностью Time в терминах Big O для этого кода ниже. Я предполагаю, что это O (N.logN).

Код приведен здесь только как пример, не претендующий на компиляцию, как он есть.

for(i = 0; i < n-1; i++)
{
 for(j = 0; j < n-i-1; j++)
 {
 if (a[j+1] < a[j])
 {
 temp = a[j];
 a[j] = a[j+1];
 a[j+1] = temp;
 }
 }
}
1 ответ

Я предполагаю, что это O (N.logN).

Зачем угадать? Посмотрите, что на самом деле происходит...

Первый раз, хотя внешний цикл, я == 0. Это означает, что j будет варьироваться от 0 до n-1.

Второй раз через я = 1, поэтому j будет варьироваться от 0 до n-2.

В-третьих, я == 2, поэтому j варьируется от 0 до n-3.

...

Последний раз через я == n-1, поэтому j варьируется от 0 до 0.

Таким образом, общее число операций равно n-1 + n-2 + n-3 +... + 0.

Какая сумма Σi, я = 0..n-1? Теперь преобразуем это в привязку большого O.

licensed under cc by-sa 3.0 with attribution.