. asdf: Algorytmy, złożoność obliczeniowa: Dany jest pseudokod: r =0; for i = 1 to n do: for j = 1 to i do: for k = j to (i+j) do: r = r+1; end end end lub w C: for(i =1;i<n;i++){ for(j=1;j<n;j++){ for(k = j;k<(i+j);k++){ r = r+1; } } } Jak obliczyć r/ lub oszacowac zlozonosc w notacji duże O?

asdf: :(

ICSP:

asdf: nikt nie wie ? Dla prostszych algorytmow potrafie oszacowac zlozonosc, ale to mnie przerasta

asdf: tak powinno byc, bo wczesniejsze bylo by za proste... for(i =1;i<n;i++){ for(j=1;j<i;j++){ for(k = j;k<(i+j);k++){ r = r+1; } } }

q: najwazniejsze to zauwazyc, ze liczba iteracji najbardziej wewnetrznej petli zmiennej k (poczawszy od drugiej iteracji zmiennej i) jest uzalezniona od i rowna wartosci samej zmiennej i; np. dla i = 3: pierwszy obieg petli: j = 1, wowczas k przyjmuje wartosci {1, 2, 3} drugi obieg petli: j = 2, k przyjmuje wartosci {2, 3, 4} // j wzroslo o jeden, wowczas (i + j) takze wzroslo o jeden −> calosc uzalezniona jest tylko od zmiennej i ilosc iteracji zmiennej i to suma: 1 + 2 + 3 + .... + (n − 1) całkowita zlozonosc (na podstawie ilosci iteracji wszystkich petli) wynosic bedzie: 1 (pierwszy i jedyny obieg petli zewn.) + 2*1 + 3*2 + 4*3 + .... + (n − 1)*(n − 2) suma ta to szukana zlozonosc; nie potrafie jej obliczyc, ale cos mi mowi, ze bedzie to O(n²)

asdf: Tu chyba też nie chodzi o to, by dokładnie to obliczyć, tylko dobrze oszacować z góry.