Jak obliczyć sumę kwadratu serii dziennika

Question

Mam algorytmu, i zorientowali się, że jego run-time złożoność następująco następujący wzór:

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 

Podstawa dziennika jest 2.

Jak dowiedzieć się, co Θ/Omicron; złożoność algorytmiczna pochodzi z tej formuły?

Answer 1

za górną granicę można rozumować similat do log (n!) = O (nlog (n))

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 < [log(n)]^2 + ... + [log(n)]^2 
                  = n[log(n)]^2 

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 = O(n[log(n)]^2) 

Aby udowodnić na dolnej granicy, trzeba pokazać, że daną sumę wynosi> = stała wielokrotność n [log (n)]^2

Usuwanie pierwszą połowę względem od sumy

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= [log(n/2)]^2 + [log(n/2 + 1)]^2 + [log(3)]^2 + ....... + [log(n)]^2 

Wymiana każdy termin z log (n/2)^2

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= (n/2) * [log(n/2)]^2 

Dolna granica = (n/2) * [log(n) - 1]^2

Możemy udowodnić, że log(n) - 1 >= (1/2) * log(n)

Stąd dolna granica = (n/8) * [log(n)]^2 i Górna granica = n * [log(n)]^2

Więc Θ([log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2) = n * [log(n)]^2