-3
Пусть A (N) = Θ (N)
B (N) = Θ (N) и
C (N) = Ω (N)
Тогда, что можно сказать о C (N) + A (N) * B (N)?
A
ответ
2
Вы можете показать, что D (n) = C (n) + A (n) * B (n) - Ω (n^2) - это следует (почти) непосредственно из определений классов сложности. Вы не можете показать что-либо на пути сверху, сложнее, поскольку C (N) может быть таким сложным, как вам нравится.
Чтобы быть более явным: пусть n_A и n_B таковы, что при n> n_A мы имеем A (n)> k_A * n и для n> n_B имеем B (n)> k_B * n. Они существуют, так как A и B, в частности, Ω (n). Помните, что C (n) неотрицательно, мы имеем для n> max (n_A, n_B): C (n) + A (n) * B (n)> A (n) * B (n)> k_A * n * k_b * n = (k_A * k_B) * n^2. Полагая k_D = (k_A * k_B), мы обнаружили, что D (n) удовлетворяет условию того, что Ω (n^2).
Смежные вопросы
- 1. Контекстная свободная грамматика для {a * b * c *} - {a^n b^n c^n | n> = 0}
- 2. Эффективный способ решения (A & N) + (B & N) + (C & N)
- 3. комплимент {a^n b^n c^n} в TOC
- 4. Определено ли поведение «a = (b + n)/++ n»?
- 5. Заменить a * b ** N на a * pow (b, N)
- 6. Prolog Parse Tree a^n b^n
- 7. Пролог: Простой DCG a^n b^n
- 8. Дополнение языка L = {a^n b^n | n! = 100}
- 9. PushDown Automaton (PDA) для L = {a^(n) b^(n) c^(n) | n> = 1}
- 10. Пускай автомат для (a^n b^n)^m c^m
- 11. Можно ли упростить O (n! + N)?
- 12. Сложность f (n) = b * n + f (n-1)
- 13. Как избежать временной сложности O (n^2)?
- 14. Докажите, что для любых a> b> 0, b^n в Big-O a^n
- 15. Matlab script a (n) = a (n-1) + a (n-2)
- 16. Соответствие a^n b^n c^n (например, «aaabbbccc») с использованием регулярных выражений в C#
- 17. O (n log n) Алгоритм сложности времени?
- 18. Являются ли L1 = {a^n b^n | n <4} и L2 = {a^n b^n | n <10^10^10}, регулярные языки?
- 19. O (n log n) vs O (n) - практические различия во временной сложности
- 20. Пример сложности экспоненциального времени (n^n)
- 21. Написать программу для обратной строки O (N) временной сложности и O (N) пространства сложности
- 22. Признать язык A^n B^n в Prolog без арифметики
- 23. Какой класс сложности O (N^N)?
- 24. Решение матричного уравнения A B = C. с B (n * 1) и C (n * 1)
- 25. Что соответствует RegEx (a + b)^n (c + d)^m?
- 26. Python - функция, которая проверяет, является ли равенство a ** n + b ** n = c ** n для n∈ {2,3, ..., 10}
- 27. Существует ли эффективный способ аппроксимации (a/b)^n, где a, b и n - целые без знака?
- 28. Что такое большой O для сложности O (sqrt (n) * log (sqrt (n))) + O (n)
- 29. (a/b) mod n для больших чисел?
- 30. REGEX: \ s \ d {3,4} \ b \ n \ n?
Может ли у плз разработать немного? –
@JonSillick: Там вы идете. Но на самом деле вам следует прочитать базовый учебник по алгоритмам или программированию и алгоритмам, где вы найдете некоторое отношение к этой теме и, возможно, несколько упражнений. Я предполагаю, что вы студент или ученик средней школы, поэтому вы также можете попросить своего учителя или ТП помочь вам обойти все это. – einpoklum
@JonSillick Я думаю, вам нужно разработать свой вопрос, если вы хотите, чтобы люди разрабатывали свои ответы. –