Witam.
Mam bardzo duzy problem z wyliczaniem zlozonosci algorytmow.
ok rozumiem jak np wyliczyc zlozonosc dla sortowania babelkowego (chociaz i tak nie mam pewnosci co do zapisywania tych jedynek jako operacji wykonywanych jednokrotnie - jak to pozniej mnozyc?):
void sortuj(int *tab, int n)
{
for(int i=0;i<n;i++) // n
{
for(int j=0;j<n-1;j++) // n-2
{
if(tab[j]>tab[j+1]) // 1
swap(tab[j],tab[j+1]) // 1
}
}
}
T[n]=n*(n-2) +1 + 1 = n^2 - 2n + 2
oczywiscie wybieramy skladnik dominujacy co daje n^2.
ale co w wypadku ciezszych kodow takich jak na przyklad quicksort? nie wiem jak patrzec na rekurencje (jak ja oznaczac etc).
bardzo prosze o pomoc bo we wtorek egzamin i wlasciwie to ostatnia rzecz ktora mi zostala do nauki.
z gory dziekuje i pozdrawiam.