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

Question

[Hi-Pyncho]

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



В JS конкатенация строк такой же сложностью оценивается?
Буду очень благодарен, если подскажите, где искать достоверную информацию по этой теме в рамках JS.

Answer 1

[Андрей Ежгуров]

1. Сложность зависит алгоритма, используемого в конкретной реализации. Потому в V8 сложность может быть совсем не такой, как в JS-движке Firefox.

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

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

Answer 2

[Wataru]

Похоже документация не указывает сложность методов. Видимо, никто не ожидает от js кода производительности =)

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

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

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

Comments

[Дмитрий]

Какое отношение сложность имеет к производительности?

[Wataru]

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

Answer 3

[Руслан Лопатин]

Представление строк в разных JS движках разное.

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