В поисках Big-O, Omega и theta

Я просмотрел ссылки, и я слишком глуп, чтобы понять механический процесс их выяснения. Я понимаю идеи O, тэты и омеги, и я понимаю «Правила». Так что позвольте мне поработать с вами над этим примером, чтобы прояснить это в моей голове :)

f (n) = 100n + logn

g (n) = n + (logn) 2

Мне нужно найти: является ли f = O (g), или f = Ω (g), или и то, и другое (в этом случае f = Θ (g))

поэтому я знаю, что 100n и n одинаковы, и оба они медленнее, чем log (n). Мне просто нужно выяснить, работает ли (log (n)) ^ 2 медленнее или быстрее. но я ничего не могу вспомнить о журналах. если log (n) больше, означает ли это, что число становится больше или меньше?

позвольте мне добавить, что моя настоящая борьба заключается в выяснении ОБОИХ омеги и тэты. По определению f (n) ‹= g (n), если существует константа c, которая увеличивает g (n), и то же самое для обратного для omega. но как мне это проверить?


algorithm big-o discrete-mathematics
person Test    schedule 03.03.2015    source источник
comment
Калькулятор Windows имеет функцию журнала. Зарегистрируйте несколько n и посмотрите, какие результаты вы получите. Что касается функции журнала: y = log (x). 10 ^ у = х. Вы можете использовать другие базы, замените 10 любой базой, которую вы используете. Я никогда не видел других значений, кроме 2 и e. (Последние называются натуральными логарифмами.)   -  person Loren Pechtel    schedule 03.03.2015

Ответы (2)


arrow_upward
1
arrow_downward

Обычно это можно понять из следующих правил:

  1. В широком смысле k < log(n)^k < n^k < k^n. Вы можете заменить k на каждом шаге любым положительным числом, и это останется верным для достаточно большого n.

  2. Если x большой, то 1/x очень близко к 0.

  3. Для положительных x и y, x < y тогда и только тогда, когда log(x) < log(y). (Иногда ведение журналов может помочь со сложными и грязными продуктами.

  4. log(k^n) = log(k) n.

  5. Для O, тета и омега вы можете игнорировать все, кроме самого большого члена, который не сокращается.

Правил 1 и 5 достаточно для ваших конкретных вопросов. Но выучите все правила.

person btilly    schedule 03.03.2015

arrow_upward
0
arrow_downward

Вам не нужно запоминать правила, а лучше изучать общие принципы.

Здесь все, что вам нужно знать, это то, что log (n) увеличивается и растет без ограничений, а также определение big-O, а именно f = O (g), если существует такой ac, что для всех достаточно больших n, f (n) ‹= С * г (п). Вы можете узнать о журнале, вспомнив, что log (n) растет, как количество цифр n.

Может ли log ^ 2 (n) быть O (log (n))? Это означало бы (используя определение big-O), что log ^ 2 (n) ‹= c.log (n) для всех достаточно больших n, поэтому log ^ 2 (n) / log (n)‹ = c для достаточно большого большое n (*). Но log ^ 2 (n) / log (n) = log (n), который неограниченно растет, поэтому не может быть ограничен c. Итак, log ^ 2 (n) = O (log (n)).

Может ли log (n) быть O (log ^ 2 (n))? Ну, в какой-то момент log (n)> 1 (поскольку он неограниченно увеличивается), и с этого момента log (n) ‹log ^ 2 (n). Это доказывает, что log (n) = O (log ^ 2 (n)) с константой c, равной 1.

(*) Если вы проявляете особую осторожность, вам нужно исключить возможность того, что log (n) будет бесконечно много раз нулю.

person Paul Hankin    schedule 03.03.2015