Троллинг на собеседовании. "Сверхбыстрый" алгоритм сортировки и огромное большое О (или наоборот)
HTML-код
- Опубликовано: 24 ноя 2022
- Когда Большое О не помогает. Будьте внимательные к реальной скорости работы алгоритмов при сравнении их характеристик
Код примера
share.linqpad.net/m4ghsq.linq
Подробности для любознательных:
rosettacode.org/wiki/Sorting_...
Эта самая компания не знает, что кром "О большого" существует еще и "о малое", а также Ω, ω и Θ и θ. И они любят оценивать в т.ч. "О большое снизу". Гуманитарии, которые начитались про матан на хабре и довольные собой дрючат выпускников технических вузов.
Просто оставлю это здесь: habr.com/ru/articles/204580/ :-)
Сортировка за линейное время существует, это сортировка подсчётом. Кроме того, хоть в этом алгоритме на первый взгляд и O(n) шагов, не у всех из этих шагов одинаковое время выполнения, и, вообще говоря, правильная оценка работы алгоритма это должна учитывать. Далее, какая-то часть библиотеки языка или даже операционная система должна эти таймеры в правильном порядке выполнить, а для этого значения нужно ... отсортировать, ба-думтс.
Троллинг был бы удачнее, если бы вы рассказали про т.н. галактические алгоритмы.
Спасибо за содержательный комментарий. Кстати, если присмотреться то сортировка таймером и сортировка подсчетом идейно очень близки. Но с таймером гораздо веселее :-).
Примером сортировки таймером может быть, например, сортировка вагонов по номерам на горке. Спускаем вагон с горки через время равное номеру вагона в минутах. В результате получаем упорядоченный состав за n минут.
@@itchatter за какое время вы выбираете нужный вагон? Мне кажется, вы получили сортировку пузырьком.
@@itchatter да, я тоже сначала хотел написать, что это сортировка подсчётом, пока не подумал про сложность работы шедулера...
мне больше нравится таймер ))0)0)
тут разве не О(1), если за константу брать наибольшее из чисел в массиве?
Хорошее наблюдение. И, кстати, очень похоже что да, но! Чтобы найти это самое большое число все равно надо будет перебрать все элементы, а это опять n.
О(1) не зависит от набора данных. Если "константа зависит от содержимого массива", то это уже не константа.
Так когда мы считаем O от чего-то, то мы выкидываем все константы и все, что очень быстро отрабатывает. В данном случае скорость перебора массива явно быстрее, чем sleер с минимальным значением. Значит, самое длинное время - при самом большом элементе. Или я вообще ничего не понял и написал херню)))
Я думал что сортировка временем это шутка пока не прочитал этот твит::» I just solved a modal stacking z-index issue by setting the z-index to the amount of time a user has spent on the page using the JS performance interface... thus every new modal opened has a higher z-index.«
оригинал: x.com/alexjgarrett/status/1711855242290077701?s=46&t=pSUUZwB1G2U9ZdLF7-sH7Q
Radix Sort для слабаков