В случае Master Theorem случаи 1 & 3 у вас есть, если f (n) = O (log b of a-e) в случае 1, я задавался вопросом, почему нужно вычесть постоянную e?Почему постоянная добавляется в случае 3?
В третьем случае основной теоремы нужно добавить константу ... Почему это так?
Что такое константа на основе?
Вы могли бы думать об этом так - давайте третьем случае в качестве примера:
f(n) = O(n^(log(b a) + e)) for e < 0 (Журнал не (а - е), а это (войти базы Ь а) - е)
Что это значит?
Давайте сначала определим одну вещь: весь блок с правой стороны - O (n^(log (b a))). Это, по существу, асимптотическое поведение функции T (n), не принимая во внимание ее часть (n).
Эта часть не совсем интуитивно понятна, но подумайте об этом, и вы увидите ее правильно. (Просто вычислите некоторые значения для f (n) = O (1), и вы увидите, что я прав. Поскольку неисключительный f (n) для всех целей и целей O (1).)
So , учитывая, что мы смотрим на 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)
The aT(n/b) часть, по сути цикл. То, что решает, сколько итераций у нас будет. Правая часть - это тело цикла. Фактическая работа. Если правая сторона асимптотически слаба в левой части, чем правая сторона меньше, и у нас есть несколько прекрасных формул, чтобы решить асимптотическое поведение, если его слабее, равное или большее. Мы объясняем или добавляем e, как я объяснял выше, чтобы узнать, больше ли оно, меньше или равно.
Мне немного сложно объяснить такие вещи в тексте, а не на моем родном языке, я надеюсь, что это было понято.
@Rubys: Спасибо за объяснение. Вопрос, в третьем вы говорите, что константа e будет понижать ее асимптотический класс, но e> 0 в моей книге? Итак, если вы добавите число> 0, вы увеличиваете асимптотический класс, нет? Поэтому в третьем случае f (n) должно быть асимптотически больше постоянным множителем, тогда nlogb a. Поэтому, чтобы быть уверенным, что он больше, вы добавляете постоянный коэффициент ... или получили его совершенно неправильно ???? –
Я написал «+ e, для e <0», и вы написали «- e для e> 0», это то же самое ^^ – Rubys
Вы пропустили N в O (N^(log_b a - e)) – SysAdmin
Константа e не является константой математики 'e', а только некоторой постоянной e! Может иметь любое имя! –