Публикации по теме 'master-theorem'
Анализ основной теоремы, часть 2: доказательство
Часть 2: Доказательство
Итак, как мы видели в Части 1 и поняли концепцию рекуррентного отношения. Теперь мы готовы понять, как работает основная теорема. Напомним, в предыдущем посте мы определили что а как количество повторений, b как коэффициент, на который мы делим наш ввод, d степень сложности, до которой выполняется работа вне повторений, а n — это размер ввода. Мы также определили, что у нас обычно есть aʲ количество подзадач, каждая из которых имеет размер n/bʲ..
Вопросы по теме 'master-theorem'
Использование основной теоремы
Используйте основную теорему, чтобы установить O() границы для этого утверждения:
T(n) = 16T(n/4) + n 2 + log n
Я пытаюсь понять основную теорему все больше и больше, пытаюсь найти больше примеров в Интернете и получить их решения.
1185 просмотров
schedule
23.02.2023
Мастер-метод - Анализ
Речь идет об анализе алгоритмов: допустим, время выполнения задачи равно:
T(n) = { 1, for n == 1 | T(n/3) + THETA(1), for n > 1}
Теперь это THETA(log base3 n)
Но, если я использую мастер-метод, я оцениваю THETA(log base2 n) ,...
509 просмотров
schedule
30.03.2024
Решение повторяемости T (n) = T (n/2) + lg n?
У меня возникли некоторые проблемы с тем, как решить рекуррентные отношения.
T(n) = T(n/2) + log2(n), T(1) = 1, где n — степень числа 2.
Это домашнее задание, так что не давайте мне ответ. Я просто думал, как запустить проблему.
На...
15181 просмотров
schedule
16.02.2023
Обозначение Big Theta — упрощение
Я использовал основную теорему для решения рекуррентных соотношений. Я уменьшил его до Θ(3n 2 -9n) . Равно ли это Θ(n 2 ) ? У меня есть еще одно повторение, для которого решение равно Θ(2n 3 - 100 2 ) . В нотации BigTheta вы всегда используете...
2126 просмотров
schedule
20.05.2023
нужно определение в Изабель, чтобы показать, что две частичные функции никогда не производят одинаковый результат
Я использую математический инструментарий HOL-Z для выполнения некоторых предикатов Изабель. в частности, я использую частичное определение функции для определения некоторых отношений в спецификации Z, которую я пишу, где я конвертирую схему в...
186 просмотров
schedule
14.04.2022
сложность функции T(N)=T(n/2)+2^n
Я учусь на курсе алгоритмов в университете. Я знаю, как применить несколько рекурсивных методов, чтобы найти эксплуатационные расходы более простых функций, но 2^n в этом вопросе вызывает у меня проблемы. Вот что я пытался применить основную...
8923 просмотров
schedule
16.11.2023
Найдите эксплуатационную стоимость алгоритма
Я не могу решить следующее повторение
T(n) = 3T(n/5) + lg^2 n
моя работа: применение основной теоремы
a=3 b=5
n^log5^3n= n^log^0.65
это приводит к n^0=1 это не сравнимо с l og^2n
Я пробовал и с деревом рекурсии, но это стало...
82 просмотров
schedule
16.04.2024
Сложность выполнения | Рекурсивный расчет с использованием теоремы Мастера
Итак, я столкнулся со случаем, когда у меня есть 2 рекурсивных вызова, а не один. Я знаю, как решить для одного рекурсивного вызова, но в этом случае я не уверен, прав я или нет.
У меня есть следующая проблема:
T(n) = T(2n/5) + T(3n/5) + n
И...
289 просмотров
schedule
04.07.2022
Как решить это уравнение рекурсии T (n) = √2T(n/2) + log n, используя основную теорему?
Я знаю, что это можно решить мастер-методом, но как? пожалуйста помоги ?
606 просмотров
schedule
25.04.2023
Повторяющееся отношение
Может ли кто-нибудь помочь в решении рекуррентной зависимости алгоритма «разделяй и властвуй» со следующим уравнением? Я почти уверен, что вы не можете использовать основную теорему здесь, потому что она не в форме T (n / b), но здесь вы можете...
44 просмотров
schedule
05.05.2023
получить сложность для алгоритма Карасубы?
Я видел вики-страницу: https://en.wikipedia.org/wiki/Karatsuba_algorithm , которая имеет рекуррентное соотношение для алгоритма Карацубы как:
T(n) = 3T(n/2) + cn + d
и с помощью мастер-алгоритма его временная сложность может быть...
99 просмотров
schedule
27.06.2022
Доказательство алгоритма сортировки и время работы
Hydrosort – это алгоритм сортировки. Ниже приведен псевдокод.
*/A is arrary to sort, i = start index, j = end index */
Hydrosort(A, i, j): // Let T(n) be the time to find where n = j-1+1
n = j – i + 1...
244 просмотров
schedule
01.07.2023
В терминах Big-O, если O (n-1) - это то же самое, что и O (n), то почему в основной теореме T (n-1) не равно T (n)?
Итак, я новичок в CS и недавно узнал о Big-O, Theta и Omega, а также об основной теореме, и на лекции я увидел, что по какой-то причине это не так, и мне было интересно, почему это так?
55 просмотров
schedule
19.08.2023
Решение 4T(n/5) + log5(n * sqrt(n)) с помощью основной теоремы
Я пытаюсь решить рекурсию 4T (n/5) + log5 (n * sqrt (n)) с помощью основной теоремы, но столкнулся с некоторыми трудностями.
Я понимаю, что использование формы T(n) = a T(n/b) + theta(n^k log^p n) даст:
a = 4
b = 5
k = 0
но как мне справиться...
112 просмотров
schedule
25.06.2022
