Почему константа добавляется в случае, если 3?

Вы можете подумать об этом так - давайте рассмотрим третий случай в качестве примера:
f (n) = O (n ^ (log (ba) + e)) для e <0 ( log не из (a - e), а скорее (log in base b of a) - e)
Что это значит?
Давайте сначала установим одну вещь : Вся капля справа - O (n ^ (log (ba))). По сути, это асимптотическое поведение функции T (n) без учета ее части f (n).
Эта часть не совсем интуитивно понятна, но подумайте об этом, и вы увидите, что все правильно. (Просто вычислите некоторые значения для f (n) = O (1), и вы увидите, что я прав. Поскольку несуществующее f (n) для всех целей и целей равно O (1).)

Итак, учитывая это, мы смотрим на e. Что делает е? Он наверняка ниже нуля, мы знаем, что благодаря ограничениям, которые мы на него накладываем, это означает, что e будет понижать асимптотический «класс» (например, n ^ 2, log n и т. Д.), Когда помещается в уравнение . Другими словами, если вы можете понизить асимптотический класс части aT (n / b) и сделать его равным f (n), то это означает aT ( n / b) асимптотически больше, чем f (n), и мы действуем соответственно.
Что это означает и в чем суть главного метода, заключается в решении следующей задачи: O (T (n) - f (n)) = O (f (n)).
Давайте посмотрим на общую форму, на которой основан главный метод:
T (n) = aT (n / b) + f (n)
aT (n / b) часть, по сути, является петлей. Дело в том, сколько итераций у нас будет. Правая часть - это тело петли. Фактически проделанная работа.Если правая сторона асимптотически слаба по отношению к левой стороне, то правая сторона имеет меньшее значение, и у нас есть несколько прекрасных формул для определения асимптотического поведения, если оно слабее, равно или больше. Мы вычитаем или добавляем e, как я объяснил выше, чтобы узнать, больше ли оно, меньше или равно.

Мне немного сложно объяснять подобные вещи в тексте, а не на моем родном языке, надеюсь, это было понято.