Почему O(1) проигрывает O(n): структуры данных в Go на реальном железе
Объясню структуры данных через очередь в поликлинике, а потом покажу, где эта аналогия ломается: почему связный список с «вставкой за O(1)» в прикладном Go обычно проигрывает обычному массиву.Спойлер: асимптотика здесь не ошибается. Ошибается вывод, который мы из неё делаем.Статья для тех, кто асимптотику знает, но не проверял её замером.ОчередьСидишь в очереди к врачу. Номерка нет, ты знаешь одно: за кем занимать.Это связный список. У элемента ссылка на следующего, и больше ничего:type patient struct { name string next *patient // «а я за вами» }
Big O от абстракции на собеседованиях к реальному коду
"Этот алгоритм работает за O(n log n)", часто вспоминается эта фраза, когда мы хотим пойти на собеседование, звучит как что-то абстрактное из учебников по алгоритмам. На самом деле Big O — это практичный инструмент описания производительности функции без привязки к конкретному железу или времени выполнения.Почему бы не пойти простым путем и не измерять время выполнения каждого алгоритма? Время сильно зависит от разных параметров, рассмотрим некоторые из них:От железа: на одном ноутбуке — 37 мс, на сервере — 12 мс...
