Какова асимптотическая временная сложность (большая тэта) для T (n) = log (n * n!)? - PullRequest
Новая
       18

Какова асимптотическая временная сложность (большая тэта) для T (n) = log (n * n!)?

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

Я думаю, что O (n * log (n)), но я не уверен.

Я пробовал log (n * n!) = Log (n (n * n-1 * n-2 * ... * 1)) = n log (n) + log (n) + log (n-1) + ... + log (1) <= nlog (n) + nlog (n) = 2n </em> log (n)

Может кто-нибудь объяснить, если это правильно

1 Ответ

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

Верхняя граница 

log(n*n!) = log(n) + log(n!)
          = log(n) + log(n) + log(n-1) + ... + log(2)
         <= log(n) + (n-1)log(n)
          = n*log(n)

Нижняя граница 

log(n*n!) = log(n) + log(n) + log(n-1) + ... + log(2)
         >= log(n) + (n-1)/2*log(n/2)                     ; 1st half >= log(n/2), 2nd >= 0
         >= log(n/2) + (n-1)/2*log(n/2)
          = (n+1)/2*log(n/2)
         >= (n/2)log(n/2)

Примечание: Здесь я предполагаю log(2)>0, что верно, если мыберут основание-2 логарифмы.Это правильное предположение, потому что отношения между логарифмами различных оснований являются линейными, а линейные отношения сохраняются с помощью big-O.

Интуитивно , мы видим, что это O(n*log(n)), право?Но почему это правда?

Чтобы понять причину, нам нужно найти C > 0 и N0 такие, что 

           (N0/2)log(N0/2) >= C*N0*log(N0)

, что уменьшает до: 

           log(N0/2)/log(N0) >= 2*C

или 

           1 - log(2)/log(N0) >= 2*C

поэтому, выбрав C < 1/2, vg C = 1/4, значение N0 нужно только проверить: 

           log(N0) >= 2*log(2) = log(4).

такдостаточно нарисовать N0 = 4.

Обратите внимание, что у нас было одно неравенство для двух констант C и N0.Вот почему мы должны были выбрать один (который был достаточно хорош), а вывести другой.

...