Когда обозначения Big O верны?

Question

Я изо всех сил пытаюсь понять концепцию больших О-нотаций. Может кто-нибудь, пожалуйста, объясните мне следующие вопросы.

Определите, верно ли следующее или нет?

i) 10 ^ (15n) ∈ O (n)
ii) nlogn ∈ O (n ^ 2)

Answer 1

Big O - это, по сути, наихудший показатель производительности.

Если у вас есть список из N объектов, и вам нужно найти один конкретный объект, и ваш алгоритм просто начинается с начала и просматривает их 1 на 1, затемв худшем случае вам нужно будет выполнить цикл N раз.

Без ответа на поставленный выше вопрос мне кажется вопросом, какой алгоритм (левая сторона) может быть выполнен в операциях Big O (правая сторона) или меньше.

Кроме того, одна вещь, которая помогла мне, когда я думаю о журнале и большом О, состоит в том, что журнал обычно относится к двоичному дереву и тому, сколько времени потребуется для перехода в это упорядоченное дерево. Это означает, что для каждого узла в дереве вам нужно выбрать только один путь.

Answer 2

Обозначение Big O дает верхнюю границу для значения функции, которое в CS используется для грубой оценки производительности функции. Вы можете найти хорошее объяснение здесь .

Скажем, например, у вас есть константа, скажем, 42. Мы говорим, что 42 = O (1), потому что есть константа k, для которого 42 <= <em>k * 1 (в данном случае 42).

Давайте рассмотрим более сложный пример: f (x) = x ^ 8 + x ^ 2 + 2. Легко видеть, что | x ^ 8 + x ^ 2 + 2 |<= | 2x ^ 8 + 2 |= O (x ^ 8). </p>