@Hi-Pyncho

Какова сложность алгоритмов (Big(O)) встроенных JS методов?

Привет!
Начал подробнее изучать оценку сложности алгоритмов. И возникло несколько вопросов:
1) Одни и те же методы в разные языках могут иметь разную сложность?
2) Где узнать официальную информацию по сложности встроенных методов в Javascript?
Я смотрел разные форумы и статьи, и иногда там одному методу присваивается одна сложность, в другом месте - другая.
Сейчас смотрю курс по оценке сложности и там, например, конкатенация строк оценивается в O(N^2)

600354fdb781f001525465.png

В JS конкатенация строк такой же сложностью оценивается?
Буду очень благодарен, если подскажите, где искать достоверную информацию по этой теме в рамках JS.
  • Вопрос задан
  • 113 просмотров
Решения вопроса 1
@eandr_67
web-программист (*AMP, Go, JavaScript, вёрстка).
1. Сложность зависит алгоритма, используемого в конкретной реализации. Потому в V8 сложность может быть совсем не такой, как в JS-движке Firefox.

2. Смотреть исходный код. Тем более, что он открыт.

Добавление к строке по одной букве - это повторение N раз конкатенации строк. Потому сложность и получается O(N**2). Никакого отношения к оценке вычислительной сложности конкатенации это пример не имеет.
В реальном мире сложность конкатенации строк длинной N и M даже в худшем случае не превосходит O(N + M).
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Похоже документация не указывает сложность методов. Видимо, никто не ожидает от js кода производительности =)

Тут ситуация еще осложняется тем, что стандарт не содержит требований по сложности. Поэтому одни и те же функции в разных браузерах, теоретически, могут иметь разную сложность.

Возможно, можно нагуглить что-то по конкретным методам.

По описанию метода concat, он возвращает новую строку не меняя аргументы. Поэтому, скорее всего, он работает за линейную сложность от общей длины операндов. Вряд ли там используется rope.
Ответ написан
Представление строк в разных JS движках разное.

В V8 строка может быть представлена как массив или как дерево. При конкатенации строк как раз используется дерево. Есть даже проект flatstr, который конвертирует древообразное представление в плоское, чтобы прочие операции над строкой выполнялись быстрее.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы