#big-o #discrete-mathematics
#большой o #дискретная математика
Вопрос:
Какая из этих функций не является O(n2)?
A. O(n2журнала2n)
B. O(вход 2(вход2n)
C. O(nlog2n)
D. (2n)2
Я считаю, что это не A, потому что в нем доминирует n2, что также сделало бы его O (n2).
Мой вопрос заключается в том, как вы определяете, какой из них не является O(n2)? Я мало работал с логарифмами, и я все еще не совсем понимаю, как с ними работать.
Спасибо.
Ответ №1:
Ответ — это
Big-O является верхней границей и в программировании представляет наихудшую среду выполнения. Например, f (n) = n ^ 2 означает, что f (n) равно O (n ^ 2) и O (n ^ 3) и O (n ^ 100 * logn). Итак, O (n ^ 2) также является O (n ^ 3), но O (n ^ 3) не является O (n ^ 2)
В случае вашего вопроса единственным ответом, который равен > n ^ 2, является A. Построение графиков функций может помочь вам визуализировать это. Как вы можете видеть, A (красный) — единственный, который увеличивается быстрее, чем n ^ 2 (черный) 
Эта статья также может помочь вам https://en.wikipedia.org/wiki/Big_O_notation и перейдите к порядку общих функций
Комментарии:
1. итак, вы хотите сказать, что в случае этого вопроса вы ищете уравнение, которое растет быстрее, чем заданное. Все, которые растут медленнее, также могут быть Big-O из n ^ 2?? но поскольку n ^ 2 является верхней границей, то, если она растет быстрее, это определенно не может быть большим O из n ^ 2?
2. Да. Все B, C, D равны O (n ^ 2), поскольку они ограничены сверху n ^ 2. С A, O (n ^ 2) является нижней границей (не верхней)
3. Еще один вопрос, который у меня возник, заключался в том, что если бы я сортировал большие O так, чтобы каждое из них было большим O следующего, мог бы я просто отобразить каждое, и если график выше другого, это означало бы, что он растет быстрее, чем другой?
4. В этом случае да. Иногда сложные функции могут сначала отображаться выше на графике, но при y = 1000000 они пересекаются. По сути, вы смотрите на то, какая из них выше, если она стремится к бесконечности.