Warum ist $ \ log n + \ log \ frac {n} {2} + \ log \ frac {n} {4} + \ log \ frac {n} {8} + \ CDs + \ log \ frac {n} {n}=Theta (\ log ^ 2 n) $?

Question

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

Die Summe der Logarithmen ist der Logarithmus des Produkts $ n \ cdot \ frac {n} {2} \ cdot \ frac {n} {4} \ cdot \ frac {n} {8} \ cdoten \ frac {n} {n} $ .Dies entspricht $ n ^ {\ log n} $ geteilt durch was?Wenn das Produkt nur $ n ^ {\ log n} $ wäre, würde dies die perfekte Sende seit $ \ log(n ^ {\ log n})=log (n) \ cdot \ log (n)=log ^ 2 n $ .Der Sivisor entspricht jedoch $ \ frac {1} {2} \ cdot \ frac {1} {4} \ cdot \ frac {1} {8} \ cdot \ frac {1}{16} \ cdots \ frac {1} {n} $ Also verstehe ich es nicht.

Answer 1

Annehmen $ N $ ist eine Leistung von $ 2 $ , Sie haben: $$ \ sum_ {i= 0} ^ {\ · · · · · · · · · · · · · · frac {n} {2 ^ i}= \ sum_ {i= 0} ^ {\ log n} \ linke (\ log n - i \ rechts)= \ sum_ {i= 0} ^ {\ log n} i= \ frac {(\ \ log n) (\ log n + 1)} {2}=theta (\ log ^ 2 n). $$