Вы можете подумать об этом так - давайте возьмем третий случай в качестве примера:
f(n) = O(n^(log(b a) + e)) for e < 0 (Журнал не из (a - e), а скорее (вход в базу b из a) - e)
Что это значит?
Давайте сначала установим одну вещь: весь блоб с правой стороны - O (n ^ (log (b a))). По сути, это асимптотическое поведение функции T (n) без учета ее части f (n).
Эта часть не совсем интуитивна, но подумайте об этом, и вы увидите, что это правильно. (Просто вычислите некоторые значения для f (n) = O (1), и вы увидите, что я прав. Поскольку несуществующее f (n) для всех намерений и целей равно O (1).)
Итак, учитывая это, мы смотрим на е. Что он делает? Конечно, он меньше нуля, мы знаем, что благодаря ограничениям, которые мы на него накладываем, это означает, что 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, как я объяснил выше, чтобы узнать, больше оно, меньше или равно.
Мне немного сложно объяснить подобные вещи в тексте, а не на моем родном языке, я надеюсь, что это поняли.