Комментарии 45
Освежите в памяти определение символа O.
Насколько я помню, сортировка пузырьком имеет оба цикла 0..length; 0..length. То что вы описали с 0..length, i..length обычно называется "оптимизированная сортировка пузырьком". Так что никакого противоречия нет, у классической сортировки пузырьком как раз N^2 итераций.
https://en.m.wikipedia.org/wiki/Bubble_sort можно посмотреть вот тут секцию Optimizing bubble sort.
Именно это и значит O(n^2)
Я бы, убрал эту статью подальше, на вашем месте. Может неплохо подпортить резюме.
Это нормальный этап в начале пути познания. Поверьте, я делал подобные вещи, когда начинал работать преподавателем, и только на 7-й 8-й год работы вышел на твёрдый хороший уровень.
Начало пути познания это школа. Не разобраться в школе с o/O нотацией -нормально. Не разобраться во время обучения в универе - уже, имхо, вопросики возникают. Не разобраться будучи "фулстек-разработчиком" - это уже прям тревожный признак, и именно то что написали в стартовом комменте.
Всё относительно :).
В школе у вас была О-нотация в программе? Хорошая школа, я о ней узнал сам лет 5-7 назад когда баловался с сортировками, на тот момент мне уже 40 было, но я и не программист как бы.
У нас - была, и да, у меня была отличная школа, но повторюсь - не знать или не разобраться в ней в школе - норм, не знать её продакт-разработчиком еще и фулстеком - очень, очень грустно
а автор является "продакт-разработчиком еще и фулстеком" (про себя молчу, я даже не понял кто это такие) И занудства ради, я бы написал "фулл-стеком", первое слово вы же правильно написали. В этом месте я могу написать что-то в таком же духе как и вы, вспомнить и школу и ВУЗ. Мне ошибки автора понятны, я сам через них прошел и совсем не отношусь к сторонникам применения О-нотации, так как она не отражает (по моему непрофессиональному мнению) сути вещей. Собственно автор об это и споткнулся.
Я вам пишу не в защиту автора, а как реакция на вашу безаппеляционность и развешивание ярлыков. У меня в школе в 9 классе (из 10-ти) появились ЭВМ "Корвет", дома у меня уже 2 года был Atari 130XE, поэтому я был единственным кто за урок успевал набрать текст в 15 строк на Бейсике. И в то время я самое интересное по программированию почерпнул из распечаток на матричном принтере, которые были на английском (я учил немецкий в школе). Так что не стоит на весь мир смотреть через очки вашего опыта, старайтесь быть более объективным.
Лирика: приезжал к нам как-то один "профессор" из Москвы, ходил плевался на всех, какие вокруг все преподаватели тупые и удивлялся почему в простом сибирском ВУЗе нет специалистов с мировым именем. Вот человек так смачно расписывается в своей глупости, хотя уверен он как раз в обратном. Вот и для меня Хабр такая же Мекка гениев.
И занудства ради, я бы написал "фулл-стеком", первое слово вы же правильно написали.
Бгг, давайте поиграем в занудство, я не против. "Фуллстеком" - еще был бы смысл написать, да и то, не особо много, но "фулл-стеком" - точно нет, т.к. тогда уж аналогом с "продакт-разработчиком" будет "фулстек-разработчик" - устоявшаяся в русском языке форма. При этом не следует путать с "full-stack developer" в английском.
Специально покопал гугол. "Фулл-стек" - 4К, "фуллстек" -16К, "фулстек" - 116К результатов, так что интуитивно подобранная форма оказалась таки наиболее подходящей.
И отдельным комментарием, чтобы не спутывать занудство с содержательной стороной.
Давайте сперва про О-нотацию и её пользу.
Мне ошибки автора тоже понятны, и я тоже в них ... кхм, вляпывался, и именно поэтому обозначил их так как обозначил. Как раз очень полезно столкнуться с ошибками сложности как можно раньше и понять, что О-нотация, даже не углубляясь в её детали с сигма и омега-версиями, позволяет легко и быстро оценивать происходящее. И понимать, что по большому счету разница между n^2 и n^2/2 в алгоритмическом плане ничтожна, если есть более приличные асимптотики (тут бы полезно в какой-нибудь практической задаче отсортировать пузырьком массив из сотни миллионов значений, потом сделать тоже самое чем-нибудь из О(n*logn), сказать "ааа, вон оно чо!" и выразительно закрыть для себя вопрос). А если уж доходит дело до детального сравнения алгоритмов одной оценки - то там еще много нюансов. Автор вон например почему-то всё содержимое внутреннего цикла за одну операцию посчитал, а их там существенно больше, и если вдруг объявится алгоритм где эта внутренняя часть в два раза меньше - то уже вопросики к оценкам будут. И еще куча других мелочей.
А теперь про вменённые мне во грехи "безапелляционность и развешивание ярлыков" (ух, как сильно)
Давайте выпишу мои безапелляционные ярлыки: "тревожный признак", "вопросики возникают", "очень и очень грустно" и то, на что я сослался в стартовом комментарии ветки - "может подпортить резюме"
Вы уж извините, но мне крайне сложно отнести эти обороты к безапелляционным. Если в вузе был курс алгоритмов в каком-то виде, то незнание нотации - это именно "вопросики возникают" вот прям буквально - вопросы к усвоенному материалу. "Тревожный признак" и "очень грустно" - это моя оценка подобного результата. Немного ярлыки, но скорее шаблонные формы. Заметьте, не "вон из профессии", не "вы непригодны" и не что-то в таком же бескомпромиссном духе (дорогой автор, если вы почему-то это читаете, не обращайте внимания, это правда не к вам). И обратите внимание, что мы сейчас их обсуждаем - что тоже кмк, плохо сочетается с безапелляционностью. Если бы привели какие-то серьезные аргументы в пользу, может даже и согласился бы с ними, но их нет. что вы тоже подчеркиваете.
К сожалению я сталкивался с работниками, которым проще было написать два... три вложенных цикла вместо того чтобы немножко подумать (и тут мозг знающий О-нотацию сразу делает из них О(n^2), О(n^3) и слегка озадачивается). Все круто когда в тесте вы вбили 3-5-10 элементов. А когда в реальной среде накапливается хотя бы 1000 значений - возникает выразительный упс. И опять же, нет проблемы если вы совершенно точно уверены в размерности данных, или быстренько проверили вопрос и выяснили что известных алгоритмов лучше просто нет (здесь снова пригодится внезапно О-нотация, поскольку её так или иначе все используют).
И в завершение, не принимайте пожалуйста слишком серьезно простыню выше. У меня скучное дежурство, а ваш комментарий почему-то зацепил, поэтому включился режим "в интернете кто-то неправ", который не успел удержать под контролем, а стирать написанное что-то неохота.
Определение О большое даётся на первом курсе матана. Хорошие нынче препы пошли, не знают программу по математике за 1й курс...
Эх. Ожидал статью уровня Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка, а оказалось, что автор просто не понимает О-нотацию.
Даже, если бы вы вышли на n² + n×5000 + 5000, и у вас в массиве будут или 10 млн. или 4 элемента или как в вашем случае - n×(n +1)/2, всё равно у вас сложность будет n²...
Тут издательство Питер рекомендовал книгу -
Алгоритмы на практике, Даниэль Зингару, там есть рассказ про нотацию О, что это значит, и почему так.
Рекомендую книгу
Вильям Спрингер
Гид по Computer Science, расширенное издание
Более того, оценка O(n100) для пузырьковой сортировки — тоже корректна. Можно оценить точнее как Θ(n2) для худшего случая
Резервировать ячейку памяти за пределами функции нет необходимости, лучше резервировать прямо в функции. Swap без третьей переменной? Вряд ли, доп. регистр процессора всё равно будет задействован. Сейчас компиляторы многое умеют оптимизировать, и лучшим стилем программирования является стиль без излишеств: от простого к чуть более сложному с осторожностью.
Swap без третьей переменной?
a = a XOR b;
b = b XOR a;
a = a XOR b;
Так это с дополнительной арифметикой :).
А как на это отреагирует компилятор - большой вопрос. Я как-то делал байтовый swap для целого числа без знака. Использовал шаблон и возможность С++20 - concept (unsigned integral). Честный код (с циклом и т.п.) компилируется в одну инструкцию ЦПУ byteswap().
В том, что это работает с числами - я уверен. А если там строки/кастомные объекты? Если побитово будет ковырять, то тоже, но я чето не уверен.
Для чисел ещё можно через сумму. Типа,
a=a+b
b=a-b
a=a-b
Какую функцию выполняет запятая после слова сортировок?
Автор молодец, провёл хороший анализ. Между прочим, можно рассказать об этом на собеседовании и получить преимущество перед другими кандидатами. Но мне кажется, что можно углубиться в тему ещё сильнее - посчитать сколько реальных опреаций (тактов, инструкций) тратится на сортировку пузырьком. Ведь очевидно, что для Си и Python сложность алгоритма (если считать её по методике из статьи) будет очень сильно различаться. Так почему на собеседованиях спрашивают сложность алгоритма без привязки к конкретному языку? С такой темой уже можно выходить на диплом.
Еще бы автор поинтересовался что такое O для которого он и сделал разоблачение. Так как то что мы увидели является обычным поверхностным пониманием темы. И перед "разгромной" статьей лучше бы спросил у более опытного коллеги: "а мои рассуждения верны?"
Как сложность алгоритма может зависеть от языка?
Скорость работы зависит, но сложность точно нет. Сложность, она же у алгоритма.
С такой темой уже можно выходить на диплом.
А там и на премию Дарвина, не грех, замахнуться
Так почему на собеседованиях спрашивают сложность алгоритма без привязки к конкретному языку?
Потому что сложность алгоритма в принципе не отражает никакой абсолютной величины (ни секунд, ни циклов процессора, ни конкретных операций), а лишь является функцией, которая показывает как будет изменяться время/память для его выполнения при изменении входных данных (количества данных, размера словаря, и т.д.). И она является характеристикой именно алгоритма, а не его реализации. Сказав что-то из статьи на собеседовании в самом лучшем случае можно получить улыбку собеседующего, а в худшем это заваленный собес.
Кроме того, в статье есть еще ряд ошибок. Например, "О большое" это и есть обозначение для "худшего случая". Который при этом может быть даже единственным возможным случаем. Т.е. какие там есть случаи кроме худшего для "О большого" в принципе не важно, и оптимизации под специфичные конфигурации входных данных на него не влияют.
А вот и зря вы так говорите. Ибо хешмапа в java, например, вопреки интуитивному представлению, что поиск в ней должен осуществляться за константное время, производит поиск отнюдь не за константное время. Корень из n, хотя такое о большое, нигде не описано.
При этом в C# Dictionnary, цитирую
Универсальный класс Dictionary<TKey,TValue> обеспечивает сопоставление набора ключей с набором значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Получение значения с помощью его ключа происходит очень быстро, близко к O(1), поскольку класс Dictionary<TKey,TValue> реализован в виде хэш-таблицы.
Как реально в коде реализовано, я не знаю.
Поэтому, если вы на собесе по java скажете, что поиск в hashMap осуществляется за O(1), вы его провалите.
Нигде не описано, а вы тогда откуда знаете :)?
Имею в виду, что O(n), есть, O(log(n)) есть, а вот O(sqrt(n)) нет, хотя у hashMap в java именно такая сложность.
Странно, конечно. Ничего особенного в O(n^0.5) нет. Должно быть в документации, если это так, а иначе откуда мы должны знать?
А откуда вообще инфа, что у него такая сложность? Не спец по java, но во всех источниках до которых дотянулся говорится что до какой-то версии был связный список с O(n), а потом хешмап улучшили, и теперь при возможности сравнения элементов используется дерево с O(log(n)).
This 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
Ну, а если не равномерно распределяет -- ССЗБ. Логарифм -- это ещё легко отделались.
И откуда это тайное знание? В коде стандартной библиотеки я вижу совершенно обычную версию поиска с закрытой адресацией. То что поиск в словаре это "амортизированное" О(1) - не меняет ничего. Тот факт, что ноды при переполнении превращаются в деревья - тоже
Если собес проводит адекватный человек, то он просто задаст наводящий вопрос. Если собеседуемый хотя бы примерно понимает как работают хешмапы, он ответит что при плохом распределении ключей время доступа может увеличиваться. На результат собеса если собеседуемый соответствует позиции такая заковырка влиять не должна.
Ох, школота... при расчете о большое, выполняются правила:
константные слагаемые выбрасываются, n+1 => n
умножение на константу выбрасываются n*1/2 => n
члены с меньшей степенью выбрасываются, n3+n2+n => n3.
О большое не говорит, сколько будет выполняться итераций, оно говорит, во сколько раз увеличится количество итераций при увеличении исходных данных в два раза. В данном случае, при увеличении размера массива в два раза количество итераций увеличится в четыре раза.
Справедливости ради, при прослушивании курсов по java почти все преподаватели, описывая алгоритмы и контейнеры, "описывали" сложность (сложно это называть это О большое) как "при поиске элемента в хешмапе, содержащей 10000 элементов, будет производится проход по ста элементам массива и еще по ста элементам массива". Вот какая это сложность? Насколько увеличится количество итерации при увеличении исходных данных в десять раз?
Истинная сложность алгоритма Bubble Sort