Количество итераций у пузырьковой сортировки

Разговоры на любые темы: вы можете обсудить здесь какой-либо сайт, найти единомышленников или просто пообщаться...
ndemidov
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 285
Зарегистрирован: 14.11.2007 (Ср) 16:23
Откуда: Earth planet

Количество итераций у пузырьковой сортировки

Сообщение ndemidov » 07.01.2015 (Ср) 13:09

Не пойму почему количество итераций для этой сортировки везде пишут как 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. И в среднем будет на половину итераций меньше, так\не?
Последний раз редактировалось ndemidov 07.01.2015 (Ср) 13:47, всего редактировалось 1 раз.
Большинство людей не понимает, что великое многообразие и красочность мира будут служить им крепчайшей душевной поддержкой на протяжении всей жизни. Иван Ефремов

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 4147
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Количество итераций у пузырьковой сортировке

Сообщение Mikle » 07.01.2015 (Ср) 13:22

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

ndemidov
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 285
Зарегистрирован: 14.11.2007 (Ср) 16:23
Откуда: Earth planet

Re: Количество итераций у пузырьковой сортировки

Сообщение ndemidov » 07.01.2015 (Ср) 13:58

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

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

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

Но разве количество итераций не будет пропорционально половине квадрата?
Большинство людей не понимает, что великое многообразие и красочность мира будут служить им крепчайшей душевной поддержкой на протяжении всей жизни. Иван Ефремов

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Количество итераций у пузырьковой сортировки

Сообщение Debugger » 07.01.2015 (Ср) 14:35

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

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

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

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

Нет.

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

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 4147
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Количество итераций у пузырьковой сортировки

Сообщение Mikle » 07.01.2015 (Ср) 16:08

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

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


Вернуться в Народный треп

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11

    TopList