Теорема Мастера с f (n) = log n

Для теоремы мастера T(n) = a*T(n/b) + f(n) я использую 3 случая:

  1. Если a*f(n/b) = c*f(n) для некоторой константы c > 1, то T(n) = (n^log(b) a)
  2. Если a*f(n/b) = f(n), то T(n) = (f(n) log(b) n)
  3. Если a*f(n/b) = c*f(n) для некоторой константы c < 1, то T(n) = (f(n))

Но когда f(n) = log n или n*log n, значение c зависит от значения n. Как решить рекурсивную функцию, используя теорему мастера?


algorithm big-o master-theorem divide-and-conquer
person amir shadaab    schedule 31.03.2013    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Вы можете найти эти три случая из статьи Википедии об основной теореме немного более полезными:

  • Случай 1: f(n) = (nc), где c ‹ logb a
  • Случай 2: f(n) = (nc logk n), где c = logb a
  • Случай 3: f(n) = (nc), где c > logb a

Теперь прямой зависимости от выбора n больше нет — все, что имеет значение, — это долгосрочная скорость роста f и то, как она соотносится с константами a и b. Не видя более подробной информации о конкретном повторении, которое вы пытаетесь решить, я не могу дать более конкретного совета.

Надеюсь это поможет!

person templatetypedef    schedule 31.03.2013
comment
Таким образом, для случая, когда f(n) = log n и a!=b, он не будет соответствовать второму случаю, поскольку c и k должны быть равны 1, но даст функцию n*log n. Итак, как мне проверить, где эта функция подходит? Извините за столько вопросов. - person amir shadaab; 01.04.2013
comment
Обратите внимание, что log n не является тета (n ^ c) для любой константы c. Единственный возможный случай, который здесь работает, — это средний, который мог бы работать, если бы у вас было a = b. Если a != b, то вы не можете напрямую применить основную теорему для решения рекуррентной ситуации и должны будете найти альтернативный подход. - person templatetypedef; 01.04.2013
comment
Это именно то, что я хотел услышать! Большое спасибо! - person amir shadaab; 01.04.2013
comment
Но как я могу решить функцию, если f (n) = log (n)? я смущен - person amir shadaab; 01.04.2013
comment
Основная теорема не всегда может быть применена. Если это не сработает, вам нужно использовать другой подход. Какое конкретное повторение вы пытаетесь решить? - person templatetypedef; 01.04.2013
comment
T(n) = a T(n/b) + log n, и у меня есть условие, что a!=b. я немного застрял - person amir shadaab; 01.04.2013
comment
Вы должны опубликовать свой конкретный вопрос в качестве еще одного примера и указать конкретные значения a и b - без них мы не сможем помочь. - person templatetypedef; 01.04.2013

arrow_upward
8
arrow_downward

Обычно f(n) должно быть полиномиальным, чтобы основная теорема применялась — она не применима ко всем функциям. Однако существует ограниченный «четвертый случай» основной теоремы, который позволяет применять ее к полилогарифмическим функциям.

Если f(n) = O(nlogba logk n), тогда< /strong> T(n) = O(nlogba logk+1 n).

Другими словами, предположим, что у вас есть T(n) = 2T (n/2) + n log n. f(n) не является многочленом, но f(n)=n log n и k = 1. Следовательно, T(n) = O(n log2 n)

См. этот раздаточный материал для получения дополнительной информации: http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf

person user3814579    schedule 01.10.2014

arrow_upward
-1
arrow_downward

Когда f(n)=log(n), основная теорема неприменима. Вы должны использовать более общую теорему, Akra–Bazzi.

В результате T(n)=O(n).

источник.

Другой способ найти более конкретное доказательство этого результата — найти доказательство вычислительной сложности алгоритма «Поиск оптимальной сортированной матрицы».

введите здесь описание изображения

person transang    schedule 25.01.2020