Каково значение f (n) в рекуррентном соотношении T (n) = aT (n/b) + f (n), и в чем смысл f (n) = 0 (n^log (база b) a - e) для некоторого e> 0; так просто хотел узнать причину этого журнала (база b) a. Я пробовал с деревом рекурсии, но запутался, так что PLZ помочь мне.Решение Рекуррентное отношение по методу хозяина и его анализ
f (n) означает, что существует функция f переменной n, представляющая размер ввода для некоторого алгоритма. T (n) дает время выполнения алгоритма для заданного размера ввода n. f (n) дает нерекурсивную компоненту этой среды выполнения.
Если f (n) = O (n^[log_b a-e]), то все в квадратных скобках является лишь некоторой константой; это эквивалентно f (n) = O (n^k) для некоторой константы k. Почему они выбрали эту константу, вопрос заключается в том, чтобы спросить их, но я подозреваю, что она была выбрана потому, что вам нужно сравнить, используя Мастер-метод, и это, вероятно, поучительное значение: выполнив мастер-метод с этим значением, вы вероятно, узнает что-то о методе мастера и его применении.
Спасибо, сэр, но смутно, что в чем причина принятия этого нерекурсивного компонента и как он вычисляется, скажем, в случае двоичного дерева поиска, что будет f (n) .i получил ответ как тета (1), но было просто смущено, что мы сравниваем число с средним элементом, поэтому в чем причина того, что он является постоянным временем, когда у нас есть более 1 среднего элемента из каждой подзадачи, которые будут сравниваться с номер для поиска. – radhika
@radhika Это O (1) для двоичного поиска, потому что для каждого вызова алгоритма количество нерекурсивной работы является постоянным. Правда, в каждом рекурсивном вызове вы делаете то же самое количество работы снова и снова, но это уже учтено Мастер-методом. Подумайте, что f (n) как «клей»; рекурсивные алгоритмы разбивают проблемы на подзадачи, решают те, которые используют один и тот же метод, затем «склеивают» куски вместе, чтобы сформировать общее решение. f (n) представляет время, затрачиваемое «клеем» на заданный размер ввода. Общая продолжительность работы - это сумма суммарного времени автономной работы по подзадачам, – Patrick87
плюс «клей» на местном этапе. – Patrick87
Если вы хотите это понять, используя дерево рекурсии, укажите 'a',' b' и 'f (n)' некоторые значения. Пример: 'a = 2',' b = 2' и 'f (n) = n'. Но если вы хотите знать, почему и как работает мастер-метод, тогда вы должны прочитать его доказательство. – arunmoezhi