Является ли log (n) = Ω (n)?

Question

Я верю, что это не так.Определение таково:

log(n) >= c*n for some n = x, and all n > x

Причина, по которой я думаю, что это не так, заключается в том, что скорость роста c * n = c.Скорость роста log (n) = 1 / n.Таким образом, при n-> бесконечность скорость роста n приближается к 0, тогда как c, скорость роста c * n, постоянна.Учитывая, что со временем log (n) будет расти медленнее, чем при любом n * c, где c> 0, n * c перерастет log (n).

Итак, несколько вопросов.

1. Можно ли предположить, что c> 0 из определения большой омеги?
2. Верна ли моя приведенная выше интуиция?
3. Я не согласен с моим доказательством выше.Поскольку для очень маленьких c, log (n) = cn очень рано, моё предположение выше подразумевает, что они будут пересекаться снова, что означает, что log (n) = cn имеет более одного решения, что кажется неправильным.

Я очень смущен и ценю помощь!

Answer 1

1- c не может быть 0 или отрицательным, поэтому вы можете предположить, что.

2- Рост log(n) ниже, чем рост n, например, для каждого n > 1,Поскольку Ω (n) - это набор функций, которые «растут больше», чем функция f(n) = n, log (n) не является Ω (n).Но вы могли бы сказать, что n = Ω (log (n)), хотя это не будет асимптотической жесткой границей.

3- В определении говорится, что неравенство может быть действительным, начиная с одного значения n0Если существует какой-то n0, вы можете сказать это.Но в этом случае (log (n) = Ω (n)) это не так, потому что он должен быть действительным для каждого n >= n0.И для любого большого значения рост log (n) ниже, чем рост n.

Answer 2

Нет, на самом деле все наоборот.

• Время работы функции log(n) равно O(n)

[читай: сверху ограничен некоторым полиномом fn, член высшего порядка которого n]

• и fn с временем работы n равно Ω(log(n))

  [читать: ограничен снизу некоторым полиномом fn, член высшего порядка которого log(n)]

Что касается вашей интуиции, это совершенно правильно. log(n)=cn встречается только в одной точке.