big-theta

2зной

2ответ

Является ли «наилучшим вариантом производительности» (1) -> время работы ≠ Θ (log n) «действительно?

Это аргумент, подтверждающий, что время работы алгоритма не может считаться Θ(f(n)), но вместо этого должно быть O(f(n)). E.g. этот вопрос о бинарном поиске: Is binary search theta log (n) or big O lo

4зной

2ответ

Какова временная сложность данного альгорта?

x=0 for i=1 to ceiling(log(n)) for j=1 to i for k=1 to 10 x=x+1 Я включил ответ, который я придумал здесь: Я думаю, что время сложность θ (п 2 лог^(п)), но я не уверен, моя логика

0зной

1ответ

Решая рекуррентность T (n) = T (n/5) + T (7n/10) + Θ (n)

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

-2зной

1ответ

алгоритмическая сложность Big O, Little O, Big Omega, Little Omega, Theta

Вот вопрос, я работаю с For each pair of expressions, indicate whether A is O, o, Ω, ω, or Θ of B. Я понимаю, в значительной степени верхняя граница и омега является нижняя граница и тета - верхняя

2зной

3ответ

Существует ли даже алгоритм для 2^(n) - 1, который лежит в Theta Ө (1)?

поэтому у меня есть вопрос об алгоритме, который я должен «изобрести»/«найти». Это алгоритм, который вычисляет 2^(n) - 1 для Ө (n^n) и Ө (1) и Ө (n). Я думал несколько часов, но не смог найти решения

0зной

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₃⋅