s=0; 
for(i=1;i<n;i=i*2) 
{ 
    for(j=0;j<n;j++)
    {
        s=s+i*j;
    } 
    s=s+1;
}

Próbuję ustanowić złożoność Big-O na powyższy algorytm. Zewnętrzna pętla zaczyna się w 1 i działa na n , licznik w i podwaja się dla każdej iteracji, a zatem jest to log (n ) zachowanie. Pętla wewnętrzna biegnie z 0 do n z o (n) zachowaniem. Jestem zdezorientowany, czy jest on o (N * log (n)) , czy nie, sprawy zamówienia czy nie? Również j zaczyna się na 0, a nie na 1, więc nie może być o (N * log (n)) ?

3
Alina Khachatrian 3 czerwiec 2018, 20:40

3 odpowiedzi

Najlepsza odpowiedź

W tym przypadku wewnętrzna pętla jest niezależna od zewnętrznej pętli. Więc możemy po prostu policzyć liczbę czasowych pętli zewnętrznej, a następnie pomnóż ją z liczbą czasów pętli wewnętrznej, a która będzie złożonością.

Liczba czasowych Pętla zewnętrzna jest log2(n), ponieważ numer jest pomnożony przez 2 za każdym razem.

Liczba czasowych biegów wewnętrznych jest zawsze n.

Tak więc złożoność będzie O(nlog2(n)).

3
Shubham 3 czerwiec 2018, 17:55

W rzeczywistości możesz liczyć, ile razy pętla wewnętrzna biegnie w prostym przypadku. Daje dobrą wskazanie asymptotycznego zachowania jako zmiany n. Oto szybki przykład JavaScript:

function count(n) {
    let count=0; 
    for(i=1; i<n; i=i*2) 
    { 
        for(j=0;j<n;j++)
        {
            count++
        } 
       
    }    
    return count
}
let n = 1024
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

n = 32768
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

n = 1048576
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

Zachowanie wygląda dla mnie (Nlog (n)) dla mnie. Dodatkowo oznacza rozumowanie pętle log(n), że każdy wykonuje n iterations będzie O(nlog(n)), ponieważ n * log(n) === log(n) * n

3
Mark Meyer 3 czerwiec 2018, 17:58

Jestem zdezorientowany, czy jest to O (N * LOG (N)), czy nie

Tak, masz rację. Tak jak wyjaśniłeś, są dziennik (n) iteracje pętli zewnętrznej i n iteracji wewnętrznej pętli, więc o (log (n) * n) całkowita złożoność.

sprawy zamówienia lub nie?

Nie ma znaczenia tutaj. na przykład O (dziennik (n) * n) == o (n * log (n))

Również J zaczyna się od 0, a nie na 1, więc nie może być O (N * LOG (N))

Nie wpłynie na złożoność. Kiedy n przechodzi do nieskończoności, zaczyna się od 0 lub zaczyna się od 1 nie ma znaczenia.

2
pjs 3 czerwiec 2018, 18:11