Конференция VBStreets

Не пойму почему количество итераций для этой сортировки везде пишут как O(n^2). Я насчитал O(n*n\2) при алгоритме ниже:

Псевдокод:

Код: Выделить всё

M[] \\ последовательность содержит от 0 до 99 элементов
j_max = 98

For i in 0 to 98
    For j in 0 to j_max
        // операция сравнения и, если нужно, перестановки значений
    j_max = j_max - 1 // уменьшаем перебираемую последовательность, т.к. наибольшее значение уже отсортировано.

Так вот благодаря тому, что с каждым повторением второго цикла последнее значение будет отсортировано, то количество итераций сокращается на 1. И в среднем будет на половину итераций меньше, так\не?

O(n^2) - это не количество, о порядок величины. То есть количество итераций пропорционально квадрату количества элементов массива.

Mikle писал(а):O(n^2) - это не количество, о порядок величины.

Мда, вот это я понять не могу пока https://ru.wikipedia.org/wiki/%CF%EE%F0 ... 7%E8%ED%FB

Mikle писал(а):То есть количество итераций пропорционально квадрату количества элементов массива.

Но разве количество итераций не будет пропорционально половине квадрата?

ndemidov писал(а):

Mikle писал(а):O(n^2) - это не количество, о порядок величины.

Мда, вот это я понять не могу пока https://ru.wikipedia.org/wiki/%CF%EE%F0 ... 7%E8%ED%FB

Mikle писал(а):То есть количество итераций пропорционально квадрату количества элементов массива.

Но разве количество итераций не будет пропорционально половине квадрата?

Нет.

Константы не учитывается в оценке алгоритма, равно как и члены младшего порядка - пишется только порядок самого старшего. Смысл в том, что мы указываем коэффициент пропорциональности времени работы.

ndemidov писал(а):разве количество итераций не будет пропорционально половине квадрата?

Таки да!
Дело в том, что половина квадрата пропорциональна квадрату, или трём квадратам, коэффициент не важен.