Распаковка вложенных списков неопределенной глубины

[alexxz]

В выводах ничего неожиданного. Сложность алгоритмов в нотации О большого всегда считается для "достаточно больших" входных данных. То есть реально начинает выполняться начиная с какого-то большого значения. Более того, для малых значений, вероятно, будет быстрее алгоритм с большей сложностью. Например, алгоритм линейного поиска в списке из 3 элементов наверняка окажется быстрее хеш-таблицы.

[daiver19]

O(n*3m)

Это некорректное использование О нотации. 3 — это всего лишь часть константы скрывающейся за О, так что асимптотически сложность везде одинаковая. Разница в константе обусловлена деталями реализации в принципе.

[PiaFraus]

> Это некорректное использование О нотации

А где можно почитать про корректность использования нотации? Сам я как-то только помню определения из вуза и по ним легко выходит, что O(n f(x)) = O( f(x) ), но про «корректность» кажется ничего не было.

[daiver19]

Ну это я и имею в виду — нет смысла сравнивать O(n) и O(3*n), т.к. они равны.

[Niccolum]

Верно говоришь, но у меня там была очепятка
Всё потому, что идёт перестройка индексов при list.pop(0) (все индексы сдвигаются влево) и list.insert(0) — все индексы сдвигаются вправо
Поэтому там таки O(n^3*m), что уже поправил

[Niccolum]

Там было О(n*3m)
Видимо, некорректно отобразилось

[Niccolum]

О(n^3*m)