Публикации по теме 'master-theorem'
Интуиция, стоящая за мастер-методом
Мастер-метод позволяет прямо определить асимптотическую сложность алгоритмов «разделяй и властвуй» вида
T(n) = aT(n/b) + f(n)
В основном вы должны помнить три случая:
Подробнее об использовании метода Master можно прочитать здесь .
В этой статье мы попытаемся увидеть интуицию, лежащую в основе метода Master, на нескольких упрощенных примерах. Позже, когда мы пройдем формальное доказательство теоремы Мастера, мы увидим, что эти упрощения не имеют значения. Но сначала давайте..
Вопросы по теме 'master-theorem'
Понимание основной теоремы
Общая форма: T(n) = aT(n/b) + f(n)
Поэтому я должен сравнить n ^ logb (a) с f (n)
если n^logba > f(n) - это случай 1 и T(n)=Θ(n^logb(a))
если n^logba ‹ f(n) случай 2 и T(n)=Θ((n^logb(a))(logb(a)))
Это правильно? Или я...
4769 просмотров
schedule
12.11.2022
Теорема Мастера с f (n) = log n
Для теоремы мастера T(n) = a*T(n/b) + f(n) я использую 3 случая:
Если a*f(n/b) = c*f(n) для некоторой константы c > 1 , то T(n) = (n^log(b) a)
Если a*f(n/b) = f(n) , то T(n) = (f(n) log(b) n)
Если a*f(n/b) = c*f(n) для...
21974 просмотров
schedule
20.08.2022
Когда на самом деле можно применить основную теорему?
Я очень расстроен по этому поводу.
В 3-м издании CLRS, стр. 95 (глава 4.5), упоминается, что такие повторения, как
T(n) = 2T(n/2) + n lg n
не может быть решена с помощью основной теоремы, потому что разница
f(n)/n^(log_b(a)) = (n lg...
3380 просмотров
schedule
11.04.2022
Базовый случай основной теоремы постоянен?
Предполагает ли основная теорема, что T(1) постоянна? Скажем, если у меня есть алгоритм с временной сложностью: T(n) = 2T(n/2) + O(1) и T(1) = O(logn), какова временная сложность этого алгоритма?
784 просмотров
schedule
09.04.2023
Алгоритмы: основная теорема
Основная теорема может использоваться для решения рекуррентных отношений, таких как T(n)= aT(n/b)+f(n) .
Итак, если f(n)=O(n) или f(n)=cn оба значения одинаковы? Могу ли я использовать основную теорему для f(n)=cn также?
247 просмотров
schedule
23.03.2024
Решение повторяемости T (n) = T (sqrt (n)) + a
Привет, я пытаюсь решить следующее уравнение с основной теоремой:
Т(п) = а; для n‹= 2
Т(n) = T(√n) + а; еще
Поскольку я нашел похожее уравнение ( Решение повторения T(n) = 2T(sqrt(n)) ) Мне интересно, правильно ли мое решение. Я получил T...
1853 просмотров
schedule
21.01.2024
Временная сложность упрощенной 3-сторонней сортировки разделов
Ниже приведен мой алгоритм, который представляет собой упрощенный алгоритм трехстороннего разделения Дейкстры для общего списка:
static <T extends Comparable> void dutchSort(List<T> list, int left, int right) {
if (left >=...
1448 просмотров
schedule
31.03.2023
Основная теорема - В лучшем случае большой О?
Я очень новичок в алгоритмах и временной сложности и просматриваю книгу. Из того, что я знаю о функции Big-Oh, она не уникальна для любого f(n), в зависимости от констант c и n 0 . Мое первое сомнение заключается в том, дает ли Основная теорема...
532 просмотров
schedule
26.05.2023
Решение T(n) = 2T(n/2) + log n
Итак, мое рекурсивное уравнение T(n) = 2T(n/2) + log n
Я использовал главную теорему и обнаружил, что a = 2, b = 2 и d = 1.
это случай 2. Таким образом, решение должно быть O(n^1 log n) , которое равно O (n log n)
Я посмотрел в Интернете, и...
261 просмотров
schedule
26.04.2023
