Perché $ \ log n + \ log \ frac {n} {2} + \ log \ frac {n} {4} + \ log \ frac {n} {8} + \ cdots + \ log \ frac {n} {n}=Theta (\ log ^ 2 n) $?

cs.stackexchange https://cs.stackexchange.com/questions/128853

  •  29-09-2020
  •  | 
  •  

Domanda

$$ \ log n + \ log \ frac {n} {2} + \ log \ frac {n} {4} + \ log \ frac {n} {8}+ \ cdots + \ log \ frac {n} {n}=theta (\ log ^ 2n). $$

La somma dei logaritmi è il logaritmo del prodotto $ n \ cdot \ frac {n} {2} \ clot \ frac {n} {4} \ cdot \ frac {n} {8} \ Cdots \ frac {n} {n} $ .Questo equivale a $ n ^ {\ log n} $ diviso per cosa?Se il prodotto sarebbe solo $ n ^ {\ log n} $ , quindi ciò renderebbe il sene perfetto dal $ \ log(n ^ {\ log n})=log (n) \ cdot \ log (n)=log ^ 2 n $ .Ma il divisore è uguale a $ \ frac {1} {2} \ clot \ frac {1} {4} \ clot \ frac {1} {8} \ {1} {8} \ Cdot \ frac {1}{16} \ Cdots \ frac {1} {n} $ Quindi non capisco.

È stato utile?

Soluzione

Assuming $ N $ è una potenza di $ 2 $ , hai: $$ \ sum_ {i= 0} ^ {\ log n} \ log \ frac {n} {2 ^ i}= \ sum_ {i= 0} ^ {\ log n} \ sinistra (\ log n - i \ giusto)= \ sum_ {i= 0} ^ {\ log n} i= \ frac {(\ log n) (\ log n + 1)} {2}=theta (\ log ^ 2 n). $$

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top