История изменений
Исправление AntonI, (текущая версия) :
Дело вообще не в сложностях, все сложности я указал правильно. У алгоритма похоже есть дефект со множеством нулей
И единиц. И двоек… ну конечно-конечно, Вы все сложности указали правильно, это алгоритм кривой. Обычно так всегда и бывает.
У вектора добавление - O(n)?
Смотря какой вектор. Если реаллокация требуется то конечно O(N)
O-нотация описывает поведение сферического вычислителя в вакууме и не учитывает особенностей подсистемы памяти и еще кучи всяких вещей.
ЗЫ если бы Вы взяли set вместо unordered_set, то при правильном подходе имели бы сложность O(n log n) вместо O(n^2). А то length++ здесь это просто какой то лютый говнокод, пардонте… :-(
Исходная версия AntonI, :
Дело вообще не в сложностях, все сложности я указал правильно. У алгоритма похоже есть дефект со множеством нулей
И единиц. И двоек… ну конечно-конечно, Вы все сложности указали правильно, это алгоритм кривой. Обычно так всегда и бывает.
У вектора добавление - O(n)?
Смотря какой вектор. Если реаллокация требуется то конечно O(N)
O-нотация описывает поведение сферического вычислителя в вакууме и не учитывает особенностей подсистемы памяти и еще кучи всяких вещей.