Я изучаю курс MIT и книгу CLRS Introduction to Algorithms . В настоящее время я пытаюсь решить повторение (со страницы 107) Т(n) = 2T(n/2) + n 4 Если я создам рекуррентное дерево, я получу: Уровень 0: n 4 Уровень 1 2(n/2) 4...

Я решил рекуррентное соотношение, которое имеет время выполнения Θ (2 ^ n), экспоненциальное время. Как найти Ω и O для одного и того же рекуррентного отношения. Я думаю, если это Θ (2 ^ n), оно также должно быть O (2 ^ n), я прав? Как мне найти...

Пытаясь понять разницу между нотациями Theta и O , я наткнулся на следующее утверждение: The Theta-notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation. Но я этого...

Я хочу рассчитать тета-сложность этого вложенного цикла for: for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < j; k++) { // statement Я бы сказал, что это n ^ 3,...

Учитывая f(x, y) и g(n) : def f(x, y): if x < 1 or y < 1: return 1 return f(x - 1, y - 1) + f(x - 1, y - 1) def g(n): return f(n, n) какова граница Большой Тета для g(n) ? Я рассудил, что, поскольку x == y,...

Насколько я понимаю, если алгоритм O(1) , он также O(n) , O(n^2) , O(n^3) и так далее, что делает его бесполезным. Например, если бы кто-то спросил меня о обозначении любого алгоритма в формате Big-Oh, я мог бы просто сказать O(n^n) , не...

Я хотел узнать больше о Big-O и нашел эту информацию: 'если f(x) = O(g(x)) скорость роста f(x) асимптотически меньше или равна скорости роста g(x) ' Что означает асимптотически в этом случае? Также мне трудно понять, почему Big-Theta не...

Я пытаюсь проанализировать наихудший порядок роста в зависимости от N для этого алгоритма: for (int i = N*N; i > 1; i = i/2) for (int j = 0; j < i; j++) { total++; } Я пытаюсь проанализировать, сколько раз будет...

Я понимаю, почему неудачный поиск в связанной хэш-таблице имеет временную сложность в среднем Θ(1+(n/m)) потому что ожидаемое количество элементов, проверяемых при неудачном поиске, равно (n/m), а общее требуемое время (включая время для вычисления...

Меня попросили проанализировать асимптотическую временную сложность следующей функции рекурсии: for-all k ≥ 1: T(n) = n + T(n/2) + T(n/4) + T(n/8) + .... + T(n/2^k) Мне удалось доказать, что: T(n) = O(n⋅log n) и T(n) = Ω(n) , но я ищу...

Я хочу решить эту рекуррентность с точностью Θ: T(n) = T(n/5) + T(7n/10) + Θ(n) Я могу решить типичный повтор, но я не знаю, что делать с этим, поскольку он не соответствует ни одному случаю основной теоремы. Любая помощь или подсказка?

можно ли n^(1 + sin n) записать как O(n^k) , где k может быть любым положительным целым числом, большим или равным 2(k>=2)? И определены ли асимптотические обозначения только для возрастающих функций с постоянной скоростью роста или их можно...