Trudno to ująć w sposób prosty do zrozumienia - Wikipedia zdecydowanie nie pomaga ;) pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu (Mówimy, że f jest dokładnie rzędu g, gdy istnieją takie stałe że n0 > 0 i c1 > 0 i c2 > 0 ...)
Ta złożoność to inaczej ilość wykonywanych operacji w zależności od wielkości danych wejściowych.
Na przykład (przykłady w C zamiast Pascala...)
int foo()
{
return 2;
}
jest oczywiście złożoności O(1) - bo zawsze jest wykonywana jedna operacja.
int foo(int var) // przekazujemy parametr typu int
{
return 2*var + 1234;
}
ten kod też jest złożoności T(3) - zawsze wykonuje 3 operacje (mnożenie, dodawanie i zwrócenie wartości). Ale przy mierzeniu złożoności liczy się tylko rząd wielkości, dlatego jest to funkcja O(1) (formalnie - istnieje taka stała c że c*1 > 3 - logiczne, prawda? :>)
Ok, coś ciekawszego:
int sum(int *array, int count)
{
int s = 0;
for(int i = 0; i < count; i++)
{ s += array[i]; }
return s;
}
jak widać, ta funkcja służy do sumowania tablicy (int *array to tablica liczb całkowitych, w zmiennej count jest liczba elementów w tablicy)
Nie możemy tutaj podać żadnej skalarnej złożoności, na przykład T(1000), ponieważ ilość operacji zależy od wielkości danych wejściowych.
Dlatego przyjmujemy n jako wielkość danych wejściowych. Teraz możemy podać złożoność - wynosi ona T(n + 2) (n dodawań + przypisanie 0 + zwrócenie wartości). Po zredukowaniu zbędnych wyrazów, otrzymujemy rząd wielkości O(n).
A coś takiego:
int abc(int *array, int count)
{
int x = 1;
for(int i = 0; i < count; i++)
{ x *= array[i]; }
for(int i = 0; i < count - 1; i++)
{ x += array[i] - array[i+1]; }
return x / 5;
}
Ta funkcja nie robi nic sensownego. Policzmy jej złożoność - przegląda tablicę wejściową (rozmiaru n) dwa razy - czyli mamy n*(dodawanie) + n*(dodawanie i odejmowanie) czyli w sumie 3*n operacji. Po poprzednich przykładach powinieneś dość łatwo wyliczyć T(3n + 3) i O(n).
I jeszcze:
int zzz(int *array, int count)
{
int s = 0;
for(int i = 0; i < count; i+=10);
{ s += array[i]; }
return s;
}
Sumujemy co 10 element tablicy złożoność to mniej-więcej T(n/10) - ale złożoność to i tak O(n).
W rzeczywistości każda funkcja która przegląda dane wejściowe stałą ilość razy (raz, dwa razy, sto razy, jedną dziesiątą raza) ma złożoność O(n).
To może dalszy przykład:
int foo(int *array, int count)
{
int x = 0;
for(int i = 0; i < count; i++)
for(int j = 0; j < count; j++)
{
x += array[i] / array[j];
}
return x;
}
Ta funkcja sumuje wszystkie możliwe ilorazy w tablicy.
Jak pisałem, każda funkcja która przegląda dane wejściowe stałą ilość razy ma złożoność O(n) - ale ta funkcja nie przegląda danych stałą ilość razy - właściwie to przegląda je n razy!
Czyli wykonujemy n razy n operacji - mamy złożoność O(n*n) == O(n^2)!
Albo taki kod (wyjątkowo kod skopiowany z wiki)
void bubblesort(int table[], int size)
{
int i, j, temp;
for (i = 0; i<size; i++)
for (j=i; j<size-1; j++)
{
if (table[j] > table[j+1])
{
temp = table[j+1];
table[j+1] = table[j];
table[j] = temp;
}
}
}
Jest to procedura sortowania bąbelkowego.
Pierwsza pętla wykonuje się n razy, a zagnieżdżona pętla wykonuje się za każdym razem coraz mniej razy.
Tutaj również jest O(n^2) operacji!
Dlaczego? Dla tablicy 3-elementowej ilość operacji wyniesie 3 (pierwszy raz)+2 (druga pętla, j zaczyna się od 1)+1 (ostatni obrót).
Dla 4-el wyniesie 4+3+2+1 operacji.
Dla n-el wyniesie n+(n-1)+...+3+2+1 = (n*(n+1))/2 operacji (suma ciągu arytmetycznego). Czyli złożonośc algorytmu to T(n*(n+1)/2)! Teraz pomijamy nieznaczące wyrazy i otrzymujemy O(n^2).
Ogólnie jeśli wykonujesz jakąś czynność pewną ilość razy zależną od wielkości wejścia złożoność wynosi O(n). A jeśli wykonujesz czynność o złożoności O(n) n razy, masz zlożoność O(n^2)
Złożoność (N3) analogicznie - wykonywanie czynności O(n2) n razy.
Złożoności log(n) i n*log(n) pominę bo z tego co widzę jeszcze ich nie macie a są trochę bardziej skomplikowane.
I wreszcie...
for i:=1 to n-1 do
for j = 1 to i+1 do
x:= x+1;
To powinieneś wiedzieć, prawie dokładnie takie same przykłady omawiałem :>
for i:=0 to n do
begin
j:=1;
while j < n do
j:=j+1;
end;
Porównaj z poprzednim, jest wbrew pozorom bardzo podobny.
for i:=1 to n do
if x > 3 then
for j:=1 to n do
for k:=5 to n do
x:=x+1;
else
for j:=1 to n do
x:=x+1;
Coś kręcisz, x nie jest nigdzie zadeklarowany. Ale ok, zakładamy że x jest parametrem funkcji.
No więc liczysz zawsze złożoność w najgorszym możliwym przypadku. jeśli x > 3 to złożoność instrukcji warunkowej wynosi (ile, hm?), a jeśli x <= 3 to wynosi tylko (no?).
A jako że instrukcja warunkowa jest wykonywana zawsze n razy, złożoność całego algorytmu wynosi (* no właśnie?*).
Rozpisałem się strasznie, mam nadzieję że chociaż trochę pomogłem i nie namieszałem (czas iść spać). Pozdrawiam...