Большой вопрос - Алгоритмический анализ

Question

Я готовлюсь к экзамену, и я нашел эту проблему в интернете, и мне было интересно, как мне ее решить.

(с базой 2 бревна)
Докажите, что log (2 n ) является членом O (log n ).

Я попробовал, но не уверен, прав ли я, так как ответа не было. Не могли бы вы помочь?

Вот моя попытка:

log 2 n - c log n & le; 0
log 2 + log n - c log n & le; 0
1 + (1- c ) log n & le; 0
(Затем я делю на лог n .)

Пример: n = 8 и c = 10 оценивается как меньше нуля. Следовательно, это true .

Мои вопросы:

1. Я правильно делаю?

2. Можно ли еще больше упростить мой ответ?

Answer 1

lg(2n) = lg(2) + lg(n).

LG (2) является константой. См. Википедия, Логарифмические тождества .

Answer 2

Длинный ответ таков:

                log(2n)       log(2) + log(n)       log(2)
lim n->infinity ------- = lim --------------- = lim ------ + 1 = 0 + 1 = 1
                log(n)        log(n)                log(n)

Поскольку отношение двух функций в пределе существует (то есть ограничено), они имеют одинаковую асимптотическую сложность.

Таким же образом, чтобы доказать, что O (n ² ) не является O (n), вы должны сделать

lim n->infinity (n^2 / n) = lim n    which tends to infinity

Выполнение этого для O (n) против O (log n) требует больше работы, потому что

lim n->infinity (n / log n)

нужно как-то обработать. Хитрость заключается в том, что вместо этого вы можете использовать производные, поскольку производные в пределе также должны быть асимптотически связаны (в противном случае их интегралы не являются, то есть исходными функциями). Вы берете производную от n, которая равна 1, и от log n, которая равна n ^-1 , после чего

lim n->infinity (1 / (1 / n)) = lim n    which tends to infinity