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

Question

У меня есть этот код сортировки ниже, который является пузырьковой сортировкой, но я думаю, что этот код не совсем O (N ^ 2). Мне было интересно, какова будет сложность вычислений по времени в терминах 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;
        }
    }
}

Answer 1

Полагаю, это O (N.logN).

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

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

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

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

...

В последний раз, i == n-1, поэтому j колеблется от 0 до 0.

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

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