Comments 7
В выводах ничего неожиданного. Сложность алгоритмов в нотации О большого всегда считается для "достаточно больших" входных данных. То есть реально начинает выполняться начиная с какого-то большого значения. Более того, для малых значений, вероятно, будет быстрее алгоритм с большей сложностью. Например, алгоритм линейного поиска в списке из 3 элементов наверняка окажется быстрее хеш-таблицы.
O(n*3m)
Это некорректное использование О нотации. 3 — это всего лишь часть константы скрывающейся за О, так что асимптотически сложность везде одинаковая. Разница в константе обусловлена деталями реализации в принципе.
> Это некорректное использование О нотации
А где можно почитать про корректность использования нотации? Сам я как-то только помню определения из вуза и по ним легко выходит, что O(n f(x)) = O( f(x) ), но про «корректность» кажется ничего не было.
А где можно почитать про корректность использования нотации? Сам я как-то только помню определения из вуза и по ним легко выходит, что O(n f(x)) = O( f(x) ), но про «корректность» кажется ничего не было.
Там было О(n*3m)
Видимо, некорректно отобразилось
Sign up to leave a comment.
Распаковка вложенных списков неопределенной глубины