Для последовательных блоков время складывается: O(n) + O(n²) + O(n³) = O(n³). При большом n доминирует самый быстро растущий член, если все оценки используют один и тот же размер входа.
Если в алгоритме есть последовательные блоки с разной сложностью, например O(n), O(n²) и O(n³), какой будет суммарная сложность?
Для последовательных блоков время складывается: O(n) + O(n²) + O(n³) = O(n³). При большом n доминирует самый быстро растущий член, если все оценки используют один и тот же размер входа.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Для последовательных блоков время складывается: O(n) + O(n²) + O(n³) = O(n³). При большом n доминирует самый быстро растущий член, если все оценки используют один и тот же размер входа.
Это не умножение, как при вложенных зависимых циклах. Постоянное количество запусков блока не меняет класс асимптотики. Если размеры независимы, например n и m, их нельзя автоматически заменить одной переменной: O(n + m²) остаётся двухпараметрической оценкой. Также Big O описывает верхнюю границу; для точной характеристики роста иногда уместнее Θ.