Potrzebuję pomocy w zrozumieniu, jak znaleźć Big-Oh segmentu kodu

Question

Finał My Computer Science II jest jutro i potrzebuję pomocy w zrozumieniu, jak znaleźć Big-Oh dla segmentów kodu. Przeszukałem Internet i nie znalazłem żadnych przykładów tego, jak potrzebuję go zrozumieć.

Oto problem z naszej próbki końcowe:

for(int pass = 1; i <= n; pass++) 
{ 
    for(int index = 0; index < n; index++) 
     for(int count = 1; count < n; count++) 
     { 
      //O(1) things here. 
     } 
    } 
} 

mamy się znaleźć zamówienia (Big-OH) algorytmu.

myślę że byłoby O (n^3) i tutaj jest jak doszedłem do tego wniosku

for(int pass = 1; i <= n; pass++) // Evaluates n times 
{ 
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
     for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
     { 
      //O(1) things here. 
     } 
    } 
} 
// T(n) = (n) + (n^2 + n) + n^3 
// T(n) = n^3 + n^2 + 2n 
// T(n) <= c*f(x) 
// n^3 + n^2 + 2n <= c * (n^3) 
// O(n) = n^3 

ja po prostu nie wiem, czy robię to prawidłowo. Czy ktoś może wyjaśnić, jak oceniać taki kod i/lub potwierdzać moją odpowiedź?

Answer 1

Tak, jest to O(n^3). Jednakże:

for(int pass = 1; pass <= n; pass++) // Evaluates n times 
{     //^^i should be pass 

    for(int index = 0; index < n; index++) //Evaluates n times 
     for(int count = 1; count < n; count++) // Evaluates n-1 times 
     { 
      //O(1) things here. 
     } 
    } 
} 

Ponieważ ma trzy warstwy zagnieżdżonej pętli zagnieżdżona pętla zostanie ocenione n *n * (n-1) razy każdej operacji wewnątrz najbardziej wewnętrznej pętli trwa O (1) czas, a więc w sumie trzeba n^3 - n^2 stałą operacji, która jest O(n^3) w porządku wzrostu.

Dobrym podsumowaniem jak mierzyć kolejność wzrostu w notacji Big O można znaleźć tutaj:

Big O Notation MIT

Cytowanie część z powyższego pliku:

zagnieżdżonych pętli

for I in 1 .. N loop 
    for J in 1 .. M loop 
     sequence of statements 
    end loop; 
end loop; 

Zewnętrzna pętla wykonuje N razy. Za każdym razem, gdy wykonywana jest zewnętrzna pętla, wewnętrzna pętla wykonuje M razy. W rezultacie instrukcje w pętli wewnętrznej wykonują łącznie N * M razy. Zatem złożoność to O (N * M). W typowym przypadku specjalnym, w którym stan zatrzymania pętli wewnętrznej wynosi J <N zamiast z J <M (tj. Wewnętrzna pętla wykonuje również N razy), całkowita złożoność dla dwóch pętli wynosi O (N^2).

Podobna racja może być stosowana w twoim przypadku.

Answer 2

Masz całkowitą rację. Na przykład jest to O (n^3).

Aby znaleźć czas działania Big Oh każdego segmentu kodu, należy pomyśleć o tym, ile razy fragment kodu wykonuje O (1) rzeczy.

Pozwól uprościć przykład dać lepsze wyobrażenie o tym:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
    { 
     //O(1) things here. 
    } 
} 

w powyższym przypadku, wewnętrzna pętla pracuje n razy dla każdego przebiegu pętli zewnętrznej. I twoja zewnętrzna pętla również działa n razy. Oznacza to, że robisz n rzeczy, n ilość razy. Robiąc to O (n^2).

Jedną z rzeczy do załatwienia jest to, że Big Oh to górny limit ograniczający. Oznacza to, że zawsze powinieneś pomyśleć o tym, co stanie się z kodem, gdy masz duży wkład (w twoim przypadku duża wartość n. Inna implikacja tego faktu jest taka, że ​​pomnożenie lub dodawanie za pomocą stałych nie ma wpływu na Wielkie oh związana np.

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < 2*n; count++) // Runs 2*n times 
    { 
     //O(1) things here. 
    } 
} 

Big oh działa czas ten kod jest także o (n^2) od o (n * (2n)) = o (n^2)

. Sprawdź również: http://ellard.org/dan/www/Q-97/HTML/root/node7.html