При изучении алгоритмов сортировок, возник вопрос об общепринятой оценке сложности, а так же к примерам реализации. И эти вопросы возникли сразу на первой сортировке Пузырьком. Заговор? Невнимательность? Небрежность? Шутка?
Согласно описанию алгоритма следует, что мы должны проходить по массиву последовательно, сравнивая 2 элемента между собой, и если первый окажется больше следующего, то меняем их местами, таким образом дойдя до предпоследнего элемента, в конце окажется самое большое значение, т.е. пузырек всплывет. И затем мы повторяем данную итерацию, но уже без учета последнего элемента, т.к. он на месте, ставя перед ним следующий элемент по порядку или очередной пузырек. Повторяем итерации до тех пор, пока не останется сравнить 2а первых элемента и на этом массив будет отсортирован. И как итог, говорится что у данной сортировки сложность в худшем случае составляет - O(n2).
Далее на просторах интернета можно встретить разные реализации данной сортировки, например (JS):
function BubbleSort(array)
{
for(i = 0; i < array.length; i++)
{
for(j = 0; j < array.length - 1; j++)
{
if(array[j] > array[j + 1])
{
var temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}И тут возникают несостыковки:
В каком случае тут может быть худший и лучший варианты, что должно прервать цикл?
По описанию сортировки, в каждой новой итерации не нужно учитывать элементы которые уже на своем месте, а тут это игнорируется.
Если придет уже отсортированный массив, то зачем в принципе делать следующие итерации
Если покопаться в других примерах, или немного подумать логически то это решается следующим примером (и снова JS):
function BubbleSort2(array)
{
var result = [...array] //Делаем копию массива, чтобы не мутировать данные
var isSorted = false //Утверждение что массив не отсортирован
var temp /*Переменная для операции обмена,
вынесена сюда чтобы сразу зарезервировать ячеку памяти,
а не создавать каждый раз при операции обмена*/
function Swap(a, b) //Вынесли операцию обмена в отдельную функцию
{
temp = result[a]
result[a] = result[b]
result[b] = temp
}
/*Можно сделать и без 3ей переменной, но думаю это избыточно,
т.к. памяти много не занимает*/
for(i = 0; i < result.length && !isSorted; i++) //Цикл прервется если массив отсортирован
{
isSorted = true //Вначале каждой итерации утверждаем что массив отсортирован
for(j = 0; j < result.length - (1 + i); j++) //Уменьшаем с каждой новой итерацией
{
if(result[j] > result[j + 1])
{
Swap(j, j+1)
isSorted = false /*Если была произведена операция обмена,
значит массив еще не отсортирован*/
}
}
}
return result
}Теперь реализация подходит под условия сортировки и достаточно логична, но есть одно НО!. Если добавить счетчик количества проходов по массиву, то получится следующая картина (возьмём наихудший сценарий, массив из 5ти элементов отсортированный в обратном порядке):
Как видно из изображения выше, последняя итерация лишняя, поэтому для первого цикла for можно взять длину (N - 1), но это совершенно не критично.
Но вот то что счетчик показал 15 вместо положенных худшему сценарию , уже странно, куда делось еще 10 операций. Или возможно все таки сложность другая? Но какая?
Ответ: Сложность сортировки пузырьком в худшем сценарии НЕ квадратичная, а равна сумме арифметической прогрессии с разностью в единицу, или или
Я понимаю что там производится несколько операций, но это K которую как правило отбрасывают, и что сложность называют приблизительно .
Но все же странно, что в такой сфере, где бывают возникают споры и из-за более мелких причин, вдруг так пренебрежительно оценивают алгоритм, хотя на выходе мы получаем разницу практически в 2 раза! Например если элементов 100, то фактически 5050 против 10000, а это почти 50%.
И стоит ли говорить о том, что если у сортировки пузырьком не квадратическая сложность, то и у остальных (нормальных квадратических сортировок) тем более.
Вывод
У сортировки пузырьком сложность , но это не делает её быстрее, это по прежнему медленная сортировка. Однако если Ваш алгоритм действительно имеет сложность
, то это практически в 2 раза хуже чем алгоритм Bubble Sort в худшем сценарии!
Комментарии (39)
GrigorGri
00.00.0000 00:00+3Насколько я помню, сортировка пузырьком имеет оба цикла 0..length; 0..length. То что вы описали с 0..length, i..length обычно называется "оптимизированная сортировка пузырьком". Так что никакого противоречия нет, у классической сортировки пузырьком как раз N^2 итераций.
https://en.m.wikipedia.org/wiki/Bubble_sort можно посмотреть вот тут секцию Optimizing bubble sort.
JekaMas
00.00.0000 00:00+7Я бы, убрал эту статью подальше, на вашем месте. Может неплохо подпортить резюме.
sci_nov
00.00.0000 00:00+1Это нормальный этап в начале пути познания. Поверьте, я делал подобные вещи, когда начинал работать преподавателем, и только на 7-й 8-й год работы вышел на твёрдый хороший уровень.
molnij
00.00.0000 00:00Начало пути познания это школа. Не разобраться в школе с o/O нотацией -нормально. Не разобраться во время обучения в универе - уже, имхо, вопросики возникают. Не разобраться будучи "фулстек-разработчиком" - это уже прям тревожный признак, и именно то что написали в стартовом комменте.
GospodinKolhoznik
00.00.0000 00:00Определение О большое даётся на первом курсе матана. Хорошие нынче препы пошли, не знают программу по математике за 1й курс...
xi-tauw
00.00.0000 00:00+20Эх. Ожидал статью уровня Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка, а оказалось, что автор просто не понимает О-нотацию.
Myclass
00.00.0000 00:00+3Даже, если бы вы вышли на n² + n×5000 + 5000, и у вас в массиве будут или 10 млн. или 4 элемента или как в вашем случае - n×(n +1)/2, всё равно у вас сложность будет n²...
Rusrst
00.00.0000 00:00Тут издательство Питер рекомендовал книгу -
Алгоритмы на практике, Даниэль Зингару, там есть рассказ про нотацию О, что это значит, и почему так.
LeshaRB
00.00.0000 00:00+1Рекомендую книгу
Вильям Спрингер
Гид по Computer Science, расширенное издание
Fil
00.00.0000 00:00+1Более того, оценка O(n100) для пузырьковой сортировки — тоже корректна. Можно оценить точнее как Θ(n2) для худшего случая
sci_nov
00.00.0000 00:00+2Резервировать ячейку памяти за пределами функции нет необходимости, лучше резервировать прямо в функции. Swap без третьей переменной? Вряд ли, доп. регистр процессора всё равно будет задействован. Сейчас компиляторы многое умеют оптимизировать, и лучшим стилем программирования является стиль без излишеств: от простого к чуть более сложному с осторожностью.
klimkinMD
00.00.0000 00:00Swap без третьей переменной?
a = a XOR b;
b = b XOR a;
a = a XOR b;
sci_nov
00.00.0000 00:00А как на это отреагирует компилятор - большой вопрос. Я как-то делал байтовый swap для целого числа без знака. Использовал шаблон и возможность С++20 - concept (unsigned integral). Честный код (с циклом и т.п.) компилируется в одну инструкцию ЦПУ byteswap().
kchhay
00.00.0000 00:00В том, что это работает с числами - я уверен. А если там строки/кастомные объекты? Если побитово будет ковырять, то тоже, но я чето не уверен.
Для чисел ещё можно через сумму. Типа,
a=a+b
b=a-b
a=a-b
mbait
00.00.0000 00:00-7Автор молодец, провёл хороший анализ. Между прочим, можно рассказать об этом на собеседовании и получить преимущество перед другими кандидатами. Но мне кажется, что можно углубиться в тему ещё сильнее - посчитать сколько реальных опреаций (тактов, инструкций) тратится на сортировку пузырьком. Ведь очевидно, что для Си и Python сложность алгоритма (если считать её по методике из статьи) будет очень сильно различаться. Так почему на собеседованиях спрашивают сложность алгоритма без привязки к конкретному языку? С такой темой уже можно выходить на диплом.
zede
00.00.0000 00:00+1Еще бы автор поинтересовался что такое O для которого он и сделал разоблачение. Так как то что мы увидели является обычным поверхностным пониманием темы. И перед "разгромной" статьей лучше бы спросил у более опытного коллеги: "а мои рассуждения верны?"
lamerok
00.00.0000 00:00+4Как сложность алгоритма может зависеть от языка?
Скорость работы зависит, но сложность точно нет. Сложность, она же у алгоритма.
GospodinKolhoznik
00.00.0000 00:00+1Ну в теории можно создать язык, в котором сложность любого цикла, например специально нелинейно увеличивалась. (А иногда не менялась, по рандому).Ну хотя бы ради лулзов, чтобы все теоретические оценки сложности шли лесом.
klimkinMD
00.00.0000 00:00+2С такой темой уже можно выходить на диплом.
А там и на премию Дарвина, не грех, замахнуться
playermet
00.00.0000 00:00+1Так почему на собеседованиях спрашивают сложность алгоритма без привязки к конкретному языку?
Потому что сложность алгоритма в принципе не отражает никакой абсолютной величины (ни секунд, ни циклов процессора, ни конкретных операций), а лишь является функцией, которая показывает как будет изменяться время/память для его выполнения при изменении входных данных (количества данных, размера словаря, и т.д.). И она является характеристикой именно алгоритма, а не его реализации. Сказав что-то из статьи на собеседовании в самом лучшем случае можно получить улыбку собеседующего, а в худшем это заваленный собес.
Кроме того, в статье есть еще ряд ошибок. Например, "О большое" это и есть обозначение для "худшего случая". Который при этом может быть даже единственным возможным случаем. Т.е. какие там есть случаи кроме худшего для "О большого" в принципе не важно, и оптимизации под специфичные конфигурации входных данных на него не влияют.
DenisPantushev
00.00.0000 00:00А вот и зря вы так говорите. Ибо хешмапа в java, например, вопреки интуитивному представлению, что поиск в ней должен осуществляться за константное время, производит поиск отнюдь не за константное время. Корень из n, хотя такое о большое, нигде не описано.
При этом в C# Dictionnary, цитирую
Универсальный класс Dictionary<TKey,TValue> обеспечивает сопоставление набора ключей с набором значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Получение значения с помощью его ключа происходит очень быстро, близко к O(1), поскольку класс Dictionary<TKey,TValue> реализован в виде хэш-таблицы.
Как реально в коде реализовано, я не знаю.
Поэтому, если вы на собесе по java скажете, что поиск в hashMap осуществляется за O(1), вы его провалите.
sci_nov
00.00.0000 00:00Нигде не описано, а вы тогда откуда знаете :)?
DenisPantushev
00.00.0000 00:00Имею в виду, что O(n), есть, O(log(n)) есть, а вот O(sqrt(n)) нет, хотя у hashMap в java именно такая сложность.
sci_nov
00.00.0000 00:00Странно, конечно. Ничего особенного в O(n^0.5) нет. Должно быть в документации, если это так, а иначе откуда мы должны знать?
playermet
00.00.0000 00:00А откуда вообще инфа, что у него такая сложность? Не спец по java, но во всех источниках до которых дотянулся говорится что до какой-то версии был связный список с O(n), а потом хешмап улучшили, и теперь при возможности сравнения элементов используется дерево с O(log(n)).
middle
00.00.0000 00:00This implementation provides constant-time performance for the basic
operations (get and put), assuming the hash function
disperses the elements properly among the buckets.https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
Ну, а если не равномерно распределяет -- ССЗБ. Логарифм -- это ещё легко отделались.
Ritan
00.00.0000 00:00И откуда это тайное знание? В коде стандартной библиотеки я вижу совершенно обычную версию поиска с закрытой адресацией. То что поиск в словаре это "амортизированное" О(1) - не меняет ничего. Тот факт, что ноды при переполнении превращаются в деревья - тоже
playermet
00.00.0000 00:00Если собес проводит адекватный человек, то он просто задаст наводящий вопрос. Если собеседуемый хотя бы примерно понимает как работают хешмапы, он ответит что при плохом распределении ключей время доступа может увеличиваться. На результат собеса если собеседуемый соответствует позиции такая заковырка влиять не должна.
DenisPantushev
00.00.0000 00:00Ох, школота... при расчете о большое, выполняются правила:
константные слагаемые выбрасываются, n+1 => n
умножение на константу выбрасываются n*1/2 => n
члены с меньшей степенью выбрасываются, n3+n2+n => n3.
О большое не говорит, сколько будет выполняться итераций, оно говорит, во сколько раз увеличится количество итераций при увеличении исходных данных в два раза. В данном случае, при увеличении размера массива в два раза количество итераций увеличится в четыре раза.
Справедливости ради, при прослушивании курсов по java почти все преподаватели, описывая алгоритмы и контейнеры, "описывали" сложность (сложно это называть это О большое) как "при поиске элемента в хешмапе, содержащей 10000 элементов, будет производится проход по ста элементам массива и еще по ста элементам массива". Вот какая это сложность? Насколько увеличится количество итерации при увеличении исходных данных в десять раз?
middle
Освежите в памяти определение символа O.
s_f1
Думаю, в данном случае не «освежите в памяти», а «узнайте».
Возможно ещё, что это очередная курсовая такая.
middle
Я старался не думать о человеке плохо.