Jak obliczyć T (N) dla tego primes algorytm Finder

Question

ten algorytm znaleźć wszystkie liczby pierwsze poniżej N

var f = function(n){ 
    var primes = [2]; //1 
    var flag; //1 
    for(var i=3; i<n; i+=2){ // (from 3 to n-1)/2 
     flag = true; //1 
     var startI = 0; // 1 
     for(var y=primes[startI]; y<=Math.sqrt(i); y=primes[++startI]){ // ??? 
      if(i%y === 0) // 1 
       flag = false; // 1 
     } 
     if(flag) // 1 
      primes.push(i); // 1 
    } 
    return primes; // 1 
} 

Dotychczas moja analiza jest wykonywana do pierwszej pętli, nie jestem pewien, jak obsługiwać druga suma (ta, która używa primes.length i Math.sqrt).

T (n) = 1 + 1 + suma ((1+ 1+ ?? dziwne suma ???) z i = 3 i n -1)/2 + 1 + 1

rozumiem jak analizować do drugiej zagnieżdżonej pętli, podejrzewam, że jest około log (N) czy coś takiego, ale chciałbym znać dokładną liczbę powtórzeń ..

pytania:

• Jak mogę obsłużyć tego rodzaju pętlę, która korzysta z tablic w pamięci do i Terate?
• Jeśli nie można uzyskać dokładnej liczby, w jaki sposób mogę uzyskać dobre przybliżenie?

Każda pomoc jest doceniana (linki do podobnych przypadków, książek itp.).

Answer 1

Wewnętrzna pętla przechodzi przez macierz wszystkich liczb pierwszych poniżej sqrt(i). Musisz więc obliczyć liczbę elementów w tej tablicy. W przypadku tablicy liczb pierwszych należy użyć przybliżenia dla π(i), liczby liczb pierwszych poniżej i.

Możesz je przybliżać przez x/ln(x) lub (znacznie lepiej) przez li(x). Więcej details here.

Do analizy x/ln(x) będzie łatwiejsze.

W sumie można się (zakładając n = 2k+1)

 
T(n) = T(n-2) + O(sqrt(n)/((1/2)⋅ln(n))) = O(Σi = 1,...,k 2⋅sqrt(2⋅i+1)/ln(2⋅i+1)) 

Otrzymasz rekurencyjnego wzoru z wewnętrznej pętli, który wykonuje iteracje nad tablicy liczb pierwszych mniejszych niż sqrt(n) (przybliżona przez sqrt(n)/((1/2)⋅ln(n))), a praca do zrobienia tak daleko, reprezentowanego przez T(n-2).

Może to uprościć jeszcze bardziej. Nie chcę się z ciebie czerpać :)

Wskazówka: Być może możesz użyć całki, aby uzyskać przybliżoną sumę. Ale myślę, że nie ma "miłego" sposobu na zapisanie tego.

Jeśli zapomnisz o -part można zobaczyć T(n) ∈ o(n3/2) i T(n) ∈ ω(n). Może możesz zrobić lepiej.

Jak wspomniano @vib, można uzyskać bardziej ścisłą górną granicę O(n3/2/ln(n)). Ale zauważ, że sqrt(n)/ln(n) jest tylko przybliżeniem liczby liczb pierwszych niższych niż sqrt(n). W ten sposób uzyskasz lepsze granice z lepszymi przybliżeniami. Ponieważ te przybliżenia nie zapewniają dokładnej wartości π(n), nie możemy nie może powiedzieć, że ten algorytm działa w Θ(n3/2/ln(n)).