Jesli ktos rozwiazylal juz takie zadania, pewnie nie bedzie mial problemu :)
Chodzi o obliczenie zlozonosci algorytmu (Notacja Wielkie O) dla paru funkcji.
Np:
- Jesli mamy mamy 1 petle FOR:
for (i= 1 ; i <n ; i++)
{ statement };
To zlozonosc tego algorytmu bedzie liniowa, O(n)
2. Jesli mamy 2 petle FOR (jedna zagniezdzona w drugiej):
for (i= 1 ; i <n ; i++)
{
for (j=1; i<n ; j++ )
{ statement };
}
To zlozonosc tego algorytmu bedzie do n do kwadratu, O(n^2), bo za kazdym 'i', wywolujemy 'j' n razy, czyli np: dla n=4, bedziemy mieli
i=1, j=1
i=1, j=2
i=1, j=3
i=2, j=1
i=2, j=2
i=2, j=3
i=3, j=1
i=3, j=2
i=3, j=3
Czyli n*n porownan = n^2 porownan.</span>
- Jaka bedzie zlozonosc algorytmu np: tego:
for (i = 1 ; i < n ; i ++)
{
for (j= i+1 ; j < n ; j++)
{
Statement
}
}
Np: dla n=3,
i=1, j=2
i=1, j=3
i=2, j .... juz sie nie wykonuje
Za pierwszym razem (dla i=1 nie wykonal sie liniowo, bo wykonal j=2 i j=3 ale przeskoczyl j=1).
Czyli wydaje sie ze jest to cos wiecej niz liniowy.
Dla i=2 natomiast nie wszedl w ogole druga petle tak wiec tutaj wykonal sie liniowo.
Jak go ogolnie zaklasyfikowac?
4. I ostatni algorytm:
int product = 1;
for ( int i = 10; i <= n; i += 10 ) {
for (int j = n; j > 0; j -- ) {
product *= ( i * j );
}
}</span>
</b></b>