но второй каждый раз меньше ибо зависит от 1.
Это же не O(n^2) да ?
Зависит от ситуации. Скажем если ты проходишь по словарю и в каждом ключе какая-то последовательность, то это будет O(n*k)
Квадрат
Там ниже пример кода
А как квадрат если например слово aba делает 6 итераций, если квадрат было бы 9
я начал отвечать до того как его увидел
Потому что это n^2 / 2 итераций, а константу мы отбрасываем
все равно зависимость в этом случае линейная. Т.е . на каждое значение внешнего цикла приходится n итераций внутреннего.
суть O в том чтобы показать главные зависимости графика времени/размера задачи.
Обсуждают сегодня