Всегда ли можно найти постоянную К, чтобы доказать большую О или большую Омегу? - PullRequest
Новая
       6

Всегда ли можно найти постоянную К, чтобы доказать большую О или большую Омегу?

0 голосов
/ 14 октября 2018

Так что я должен выяснить, является ли n ^ (1/2) Большой Омегой из log (n) ^ 3.Я почти уверен, что это не так, поскольку n ^ (1/2) даже не входит в границы log (n) ^ 3;но я не знаю, как доказать это без ограничений.Я знаю, что определение без ограничений:

g (n) - большая Омега f (n), если есть константа c> 0 и целочисленная константа n0 => 1 такая, что f(n) => c g (n) для n => n0

Но могу ли я действительно всегда найти константу c, которая будет удовлетворять этому?

, например, дляlog (n) ^ 3 => c * n ^ (1/2), если c = 0,1 и n = 10, тогда мы получаем 1 => 0,316.

1 Ответ

0 голосов
/ 14 октября 2018

При сравнении sqrt(n) с ln(n)^3 происходит следующее: 

ln(n)^3 <= sqrt(n)                         ; for all n >= N0

Откуда я знаю? Поскольку я распечатал достаточно образцов обоих выражений, чтобыубедить себя, кто доминировал над другими.

Чтобы увидеть это более формально, давайте сначала предположим, что мы уже нашли N0 (мы сделаем это позже), и давайте докажем по индукции, что если неравенство выполненодля n >= N0 это также будет выполняться для n+1.

Обратите внимание, что для простоты я использую ln в базе e.

Эквивалентно, мы имеемчтобы показать, что 

ln(n + 1) <= (n + 1)^(1/6)

сейчас 

ln(n + 1) = ln(n + 1) - ln(n) + ln(n)
          = ln(1 + 1/n) + ln(n)
         <= ln(1 + 1/n) + n^(1/6)          ; inductive hypethesis

Из определения e мы знаем 

        e = limit (1 + 1/n)^n

с логарифмами 

        1 = limit n*ln(1 + 1/n)

Следовательно, существует выход N0 такой, что 

        n*ln(1 + 1/n) <= 2                 ; for all n >= N0

, поэтому 

        ln(1 + 1/n) <= 2/n
                    <= 1

Используя это выше, мы получим 

        ln(n + 1) <= 1 + n^(1/6)
                  <= (n+1)^(1/6)

, как мы хотели.

Теперь у нас есть задача найти некоторые N0 такие, что 

ln(N0) <= N0^(1/6)

давайте возьмем N0 = e^(6k) для некоторого значения k, которое мы получимсобираюсь найти.Мы получаем 

ln(N0) = 6k
N0^(1/6) = e^k

, поэтому нам нужно только выбрать k так, чтобы 6k < e^k, что возможно, потому что правая сторона растет намного быстрее, чем левая.

...