Описание тега master-theorem

Описание тега Вопросы с тегом
In the analysis of algorithms, the Master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.
1 ответ

Основная теорема с Log n рекомбинацией

Как я понимаю основную теорему, алгоритм может быть определен рекурсивно как: a T(n/b) + O(n^d) Где a - количество подзадач, n/b - размер подзадач, а O(n^d) - время рекомбинации подзадач. Расчет временной сложности основной теоремы происходит следую…
17 май '13 в 00:15
1 ответ

Решение уравнения с использованием обобщения основной теоремы

Я прошу помощи в объяснении, как работает доказательство. Я видел примеры этого, но мне трудно понять это. Докажите следующее Решение уравнения T (n) = aT (n / b) + Θ (nk logp n), где a ≥ 1, b> 1, p ≥ 0 T (n) = O (nlogb a), если a> bk T (n) = O (nk …
29 ноя '16 в 05:07
1 ответ

Оценка сложности рекурсивной функции

void f(int n) { if (!n) return; for (int i=0; i<8; i++) f(n/12); g(n,3); } void g(int n, int i) { if (!i) return; for (int j=n; j>0; --j) { g(n,i-1); } } Я пытаюсь оценить сложность этой функции. Вот как я это делаю: Оцените данную сложность. …
20 июн '17 в 19:10
0 ответов

Применение основной теоремы

Я пытаюсь готовиться к экзаменам, глядя на свои среднесрочные результаты. Одна вещь, которую я не понимаю полностью, это основная теорема. Я понимаю, что есть три случая, и могу применить их, когда они находятся в этой форме T(n) = 25T(n/5) + n^(2) …
03 дек '14 в 21:23
1 ответ

Примените основную теорему о T(n) = T(n/2) + n

Я просто пробовал свои силы в основной теореме и немного запутался, когда пытался оценить T(n) = T(n/2) + n. Используя основную теорему, ответ оценивается как O(n). Но просто пройдите приведенный ниже код: fun(n) { if(n == 1) return ; for(int i=1;i&…
27 июл '14 в 12:01
1 ответ

Почему третий случай основной теоремы здесь не применим T(n)=2T(n/2)+nlgn

Почему nlgn полиномиально больше n, когда:"Полиномиально больше" означает, что соотношение функций падает между двумя полиномами асимптотически Здесь n^0,1 Вот график зависимости y=n^0.1,y=log n и y = n^0.4 https://www.desmos.com/calculator/vjq0j1ri…
05 апр '18 в 17:24
1 ответ

Не является положительным, если следующее решение является случаем 3 основной теоремы

Поэтому мне было интересно, будет ли считаться, что следующее повторение подпадает под случай 3 основной теоремы: T(n)=4T(n/2) + 10000 - 5000sin(n). Поэтому я обозначил свой ответ следующим образом:A = 4, B = 2, F (N) = 10000 - 5000sin (n) п ^ к = п…
11 июн '18 в 03:00
1 ответ

Временная сложность построения BST с использованием предзаказа

Я попытался написать программу для построения бинарного дерева поиска, используя последовательность предварительного заказа. Я знаю, что есть много решений: алгоритм min / max, классическая (или "очевидная" рекурсия) или даже итерация, а не рекурсия…
11 май '16 в 16:29
1 ответ

Пример для алгоритма с разделением больше чем n

Я делал вывод для теоремы мастеров, используя метод дерева, и я кое-что заметил. Итак, мы имеем: $ T (n) = a * T (n / b) + n ^ c $ Отсюда: мы замечаем, что последний уровень дерева будет иметь $a^(log_b_n)$ split, что равно $n^(log_b_a)$ Теперь, есл…
18 янв '17 в 12:03
1 ответ

Основная теорема - проблема второго случая

Даны следующие рекурсивные уравнения: T(n) = 5T(n/5)+(5sin^5(5n^5)+5)*n T(n) = T(n/4)+2sin^2(n^4) Я легко вижу, что оба уравнения соответствуют 2-му случаю основной теоремы, но из-за того, что грех является круговой функцией, кажется, что достаточно…
06 сен '13 в 15:21
1 ответ

Вопросы доказательства основной теоремы

Я читаю книгу CLRS(Введение в Алгоритмы, 3-е издание) и нахожу, что в доказательстве основной теоремы есть ошибка. На странице 104, чтобы распространить доказательство на все целые числа, используется одно неравенство, которое кажется неверным. В кн…
19 фев '14 в 10:34
1 ответ

Основная теорема и повторение

Мне дают рецидив T(n) = 3T(n/2) + n^2 lg(n) Можно ли использовать основную теорему, чтобы найти T(n) = theta(f(n))? Существует полилогарифмическая функция как f (n), но, как я понимаю, есть ограниченный 4-й случай. Подойдет ли этот 4-й случай здесь?
07 фев '16 в 21:30
1 ответ

Способ решения заявленного повторения?

Нужна помощь в поиске метода для решения следующих задач:Дано f(n) быть 9f(n/3)+(n2)*(log3n) для всех n > 1,И учитывая f(1)=1,Решить для f(n) Я попробовал основную теорему, но все 3 случая здесь не подошли, я думаю, будет использовать метод подст…
04 мар '12 в 12:46
1 ответ

Найти формулу замкнутого конца для рекуррентного уравнения по основной теореме

Можем ли мы решить это T(n) = 2T( n/2 ) + n lg n Основная теорема об уравнении рекуррентности Я исхожу из ссылки, где он заявляет, что мы не можем применить здесь основную теорему, потому что она не удовлетворяет ни одному из условий 3ree случая. С …
04 окт '12 в 11:23
1 ответ

Какова будет временная сложность следующего рекурсивного алгоритма?

Какова будет сложность следующего рекурсивного алгоритма? void rec(n){ if(n<=0) return; else rec(n/3)+rec(n/2); }
07 дек '18 в 05:11
2 ответа

Является ли nlog(n) Big Theta(n)? Основная теорема

Находится ли n⋅log(n) в Θ(n)?Я спрашиваю это, потому что я решаю повторения, используя основную теорему. Уравнение T(n) = 2T(n/2) + n log n Решение говорит, что оно удовлетворяет случаю 2, что означает T(n) = Θ(n log(n)). Я не понимаю, как n log (n)…
17 окт '14 в 22:55
0 ответов

Решение T(n) = 4T(n/2) + тета (n^2 / logn)

Я пытаюсь решить T(n) = 4T(n/2) + тета (n^2 / logn) Я хочу использовать Master Метод но не уверен как доказать n^2 >> (n^2 log^-1n) Любая помощь очень ценится! Спасибо!
24 янв '19 в 23:35
1 ответ

Основная теорема: Как найти значение b в этом рекуррентном соотношении

Основная теорема используется с повторениями вида T(n) = aT(n/b) + f(n) где a >=1 и b > 1, и в этом случае значение b может быть легко видно из повторения, однако у меня есть повторение вида T(n) = T((n/4)+3) + f(n) Как я могу получить б?
27 сен '16 в 23:29
1 ответ

Решение рекуррентности T(n) = T(n / 2) + O(1) с помощью основной теоремы?

Я пытаюсь решить рекуррентное отношение, чтобы выяснить сложность алгоритма, используя основную теорему и ее концепции рекуррентности, как я могу доказать, что: T(n) = T(n/2)+O(1) является T(n) = O(log(n)) ? Любое объяснение будет оценено!!
21 май '13 в 23:32
2 ответа

Рекуррентное соотношение алгоритма сложности

int function(int n){ if (n<=1) return 1; else return (2*function(n/2)); } Каково рекуррентное отношение T(n) для времени выполнения и почему?
22 янв '16 в 23:15