Еще раз про Big O и почему он бесполезен в JavaScript

Есть целое направление в математике - оценка сложность алгоритма. Суть которой оценить какой алгоритм эффективнее другого.

Big O - это один из методов оценки временной сложности алгоритма. Таких методов больше десятка разных. В JS сообществе получило распространение именно Big O по причине того, что на JS собеседованиях и в разных видео стали упоминать именно его игнорируя прочие.


Почему Big O в JS это проблема.
Оценка сложности алгоритма оценивает только сам алгоритм который был поставлен на вход той методологии которую мы выбрали.

Он не оценивает стоимость имплементации этого алгоритма конкретным инструментом. Например языком программирования JS.

Проблемы с оценкой становятся столь большими, сколь высоким уровнем абстракции пользуется выбранный инструмент. Язык JavaScrtip - это язык программирования с наибольшим уровнем абстракции.

Иными словами, мы имеем дело со сферическим конем в вакууме. Когда оценка самого алогритма может радикальным образом расходиться со временем демонстрируемой самой реализацией.

Простой пример:
Реализация типа Array в V8 (реализации JS) устроена таким образом, что V8 самостоятельно выделает некоторый минимальный обьем оперативной памяти для обслуживания 4 елементов пустого Array.

В том случае, если происходит ситуация, когда все 4 слота использованы, то есть мы добавили в наш Array 5 элемент, это приводит к тому, что V8 выделяет новую память в два раза больше чем ранее, КОПИРУЕТ в нее все элементы массива.

Память использованная ранее, помечается на очистку GC.

Теперь представим ситуацию, когда наш алгоритм требует оперированием не 4 элементов, а например 4 000 000 000 эллементов. Представте ситуацию, когда все Слоты выделенные для этого Array уже заполнены. И тут алгоритм добавляет еще один элемент.

Это заставит V8 скопировать 4 миллиарада эллементов в область памяти, которая согласно его алгоритму будет умножена на два. То есть потребует 8 гб памяти. Если оперативной памяти будет не достаточно, и мы работаем в системе, которая использует swap (дисковые IO) для решения подобных вопросов, то это приведет к интенсвиным IO с диском.

Представим дальше, что наш алгоритм удаляет этот элемент из нашего 8млрд массива.
Это приведет к обнулоению этой области памяти создания другой в два раза меньше. Снова IO со свапом.

А теперь мы снова добавили элемент. И снова выделение памяти и снова IO.

И теперь представим алгоритм, реализующий иную сложность, но потребляющий меньше памяти на столько, чтобы не попадать в коллизию выделения/обнуления памяти.

Какой алгоритм будет работать быстрее?
Нам уже нужно учитывать не только итерации, не только память, но и то, как быстро работает наше дисковое IO, какие лагоритмы используются там - и так далее.


Как следствие, оценка временной сложности реализации алгоритма на языке JS, оказывается невозможной, без оценки возможностей самой реализации самого языка JS.

Как следствие, BIG O, без учета особенностей имплементации V8 это сферический конь в вакууме. Который может дать как правильный прогноз так и совершенно противоположный.


Другой пример из области теоретической механики
Кто учился на специальностях подобных инфизу, наверняка проходил курс Теоретической механики.
И должны помнить один из ее парадоксов:
Пусть у нас есть катушка с намотаной на нее ниткой.
Пусть отмотана часть нитки.
Что будет если потянуть за эту нитку?
Ответ - катушка будет наматывать нитку за которую мы тянем.
Это следствие упрощений теормеха.


Так вот Big O - это теоретическая механика, которая тем больше точна, чем ближе мы к тому набору упрощений которые используются для ее работы.

В случае Big O - наиболее точная оценка дается если алгоритм реализован на языке ассемблера. И тем меньше чем выше уровень абстракации. В случае языка JS эта оценка может давать совершенно противоречивые результаты, в силу того, что под каждой строкой кода, лежит СВОЙ алогоритм издержки на реализации которого могут оказаться очень дороги.