Описание тега big-theta
Big-Theta - это асимптотическое обозначение, которое означает, что функция жестко ограничена сверху и снизу другой функцией. Другими словами, функция f является Big-Theta функции g, если f является Big-Oh для g и Big-Omega для g.
1
ответ
Как решить следующие повторения и найти привязку к тэте
T (n) = T (n-1) + n ^ c T (n) = T (n-1) + c ^ n где с постоянная
21 фев '16 в 22:52
1
ответ
Проверка большой тэты, маленькой ох и маленькой омеги с ограничениями?
Скажем, у нас есть две функции f (n) и g(n). Если бы мы хотели проверить, мало ли f (n) oh o (g (n)), было бы правильно сделать следующее: lim n -> infinity f(n)/g(n) and the result would have to = 0 ? Так что, если вышеприведенное выходит до 0, …
12 окт '14 в 00:49
1
ответ
Большое тета-время выполнения этой рекурсивной функции
Мне нужна небольшая помощь в определении времени работы Big-Theta для этой функции. int recursive(int n) { sum = 0; for (int i = 1; i <= n; i++) sum++ if (n > 1) return sum + recursive(n-1); else return n; } Я знаю, каково было бы время выполн…
03 фев '13 в 01:35
1
ответ
Временная сложность функции со временем 1 + 8 + 27 + 64 + ... + sqrt(n)^3?
Мне сказали, что 1 + 8 + 27 + 64 +... + (√n)3 = Θ (n2) Почему это так?
04 май '13 в 17:43
2
ответа
Решить повторение: T(n) = T(n^(1/2)) + Θ(lg lg n)
Начал изучение алгоритмов. Я понимаю, как найти тэта-нотацию из "регулярного повторения", такого как T(n) = Tf(n) + g(n), Но я потерян с этим повторением: проблема 1-2e: T (n) = T (√n) + Θ (lg lg n) Как выбрать метод для поиска тета? И что это за по…
22 июн '12 в 01:34
2
ответа
f(n)/log(n) = O(g(n)) ⇒ g(n) = Θ(f(n))?
Можно ли показать, что f(n)/log(n) = O(g(n)) => g(n) = Θ(f(n))? Прямо сейчас я стою здесь: f(n)/log(n) = O(g(n)) ⇒ f(n)/log(n) ≤ c₁⋅g(n) ⇒ f(n)/(c₁⋅log(n)) ≤ g(n) g(n) = Θ(f(n)) ⇒ c₂⋅f(n) ≤ g(n) ≤ c₃⋅f(n) Тогда я говорю: c₂ = 1/(c₁⋅log(n)) ⇒ c₂⋅f…
13 мар '15 в 15:47
1
ответ
Является ли функция этажа (log n)! O(n), Ω(n) или Θ(n)?
Я очень смущен тем, как я могу оценить пол (журнал n)!
03 сен '15 в 19:08
0
ответов
Нужна помощь Понимание сложности времени в Θ-нотации
У меня есть следующий код: sum = 0 ; i = n while( i ≥ 1){ for ( j = 0 ; j < n^4 ; j++ ){ sum++ ; } i = i/3 ; } Я должен найти сложность времени в нотации в терминах n, и я не уверен, как подойти к этому.
08 июн '17 в 19:52
1
ответ
Не могу рассчитать скорость роста функции
Здравствуйте, я пытаюсь решить вопрос на изображении выше, но я не могу. В частности, мой вопрос о C(n) на изображении, в конце я получил "7logn + n^(1/3)". мы знаем, что левая сторона знака +, "7logn<=n для всех n>7 (свидетель c=1, k=7)", и правая…
05 май '17 в 20:37
1
ответ
Пример рекурсивного алгоритма в Java с Θ( log n)
Я искал много дней, я пробовал много примеров рекурсивного алгоритма, но я не мог найти алгоритм, который имеет Θ( log n ) Продолжительность. Знаете ли вы какой-нибудь алгоритм рекурсии в Java, которые имеют функцию T(n) = Θ( log n ), куда T(n) явля…
10 фев '14 в 16:15
1
ответ
O(logn) и алгоритм отношений
Я до сих пор не могу понять анализ алгоритма O(logn) Таким образом, если есть вложенный цикл for, где его внутренний цикл увеличивается / уменьшается либо умножением, либо делением, то это Big-theta (logn), где его основание - на сколько оно делится…
15 июн '17 в 12:50
4
ответа
Как рассчитать биг-тета
Может ли кто-нибудь дать мне пример реального времени для расчета больших тэта. Является ли большая тета чем-то вроде среднего случая (мин-макс)/2? Я имею в виду (минимальное время - большой O)/2 Пожалуйста, поправьте меня, если я ошибаюсь, спасибо
17 сен '11 в 10:11
2
ответа
Алгоритм анализа (Big O и Big Omega)
Я неправильно понял этот вопрос на экзамене: назовите функцию, которая не является ни O (n), ни Omega(n). После попытки самостоятельно изучить этот материал через YouTube, я думаю, что это может быть правильный ответ: (n3 (1 + sin n)) не является ни…
14 дек '12 в 01:30
1
ответ
Продолжительность цикла до i*i <= n
Вот код: int foo(int n) { if(n == 1) return 1; int f = 0; int i; for(i=1; i*i<=n; i++) if(n%i == 0) f+=2; i--; if(i*i == n) f--; return f; } Моя проблема в том, что я не могу определить Θ для этого цикла,Я думаю, что это квадратный корень (n), но…
18 окт '13 в 09:28
1
ответ
Может кто-нибудь объяснить, почему это время работы подходит для этого?
Алгоритм выполняется за время n^2 + 3n + 5 для всех входных данных с размером, большим или равным 500, и за время 2^(2n) для всех входных размеров, меньших 500. Выберите все истинные утверждения снизу: 1: Its running time is O(2^(n)) 2: Its running …
11 дек '16 в 22:45
2
ответа
Тета время выполнения рекурсии
Как рассчитать время исполнения Theta для данного кода: void f(int n) { for (int i=3; i<n; ++i) for (int j=0; j<i; ++j) f(n-1); } Пока что я получил это, но я не знаю, правильно ли это или как перенести это в тета-нотацию. f(n) = n^2 * f(n-1) …
07 июн '12 в 12:06
1
ответ
Big-O & Big-Theta: сложность времени цикла O(1)?
У меня проблемы с пониманием, что именно означают Big-O и Big-Theta. Может кто-нибудь объяснить, что это означает для иллюстрации? Учитывая, что n является константой, является ли цикл for O(1) временной сложностью для худшего случая? Кроме того, яв…
16 фев '16 в 06:58
3
ответа
Как получить Омега (н)
У меня есть формула a(n) = n * a(n-1) +1; а (0) = 0 Как я могу получить Omega, Theta или O Notation из этого без основной теоремы, или у кого-нибудь был хороший сайт, чтобы понять объяснение
03 май '15 в 15:26
1
ответ
Доказательство или опровержение Ω(n) = ω(n) U Θ(n)
Является ли Ω(n) = ω(n) ∪ Θ(n) истинным или ложным? Как я могу это доказать? Я уже пытался использовать определения Ω(n), ω(n) и Θ (n), и мне кажется, что это естественно. Это все равно что доказать, что {1,2,3} = {1,2} U {3}.. как я могу доказать э…
27 ноя '14 в 15:01
1
ответ
Нахождение бета-тета-обозначения функции
Итак, у меня есть цикл, встроенный в цикл здесь: int a,b,n; for (a = 1; a <=n; a++) { for (b = 0; b < n; b+=a) cout << "hey" << endl; } n является степенью 2 Я пытаюсь понять, как рассчитать сложность Времени, но у меня возникли пр…
16 сен '14 в 03:45