Złożonoś Obliczeniowa

[sokarsg-1]

Witam

Czy mógłby mi ktoś powiedziec co to jest złożoność obliczeniowa algorytmu i jak się ją liczy, ewentualnie podać link do jakiegoś poradnika?

[Ragnor]

Tak ogólnie, to złożoność obliczeniowa agorytmu jest to zależność pomiędzy czasem wykonania algorytmu a rozmiarem danych wejściowych. Kilka przykładowych klas złożności to:

- logarytmiczna

- liniowa

- wielomianowa

- wykładnicza

 

A teraz jakiś przykład.

Mamy algorytm, który sumuje ciąg liczb naturalny. Algorytm nasz działa na jednej, jednoprocesorowej maszynie, dodaje on kolejne elementy ciągu aż dojdzie do końca. Zakładamy, że dodanie dwóch liczb naturalnych jest stałe czasowo (zajmuje jakiś czas C).

Wtedy, jeśli jako dane wejściowe damy ciąg 100 elementowy to czas działania algorymu będzie wynosić około 100*C, gdy damy dane dwa razy większe czyli 200 elementów to wtedy czas będzie wynosić około 200*C. Widać więc, że czas zmienia się wprost proporcjonalnie do rozmiaru danych, czyli taki algorytm ma liniową złożoność (O(n)).

Edytowane 16 Stycznia 2007 przez Ragnor

[Haquim]

Witam

Czy mógłby mi ktoś powiedziec co to jest złożoność obliczeniowa algorytmu i jak się ją liczy, ewentualnie podać link do jakiegoś poradnika?

Proponuję :google: Złożoność obliczeniowa

[sokarsg-1]

Tak ogólnie, to złożoność obliczeniowa agorytmu jest to zależność pomiędzy czasem wykonania algorytmu a rozmiarem danych wejściowych. Kilka przykładowych klas złożności to:

- logarytmiczna

- liniowa

- wielomianowa

- wykładnicza

 

A teraz jakiś przykład.

Mamy algorytm, który sumuje ciąg liczb naturalny. Algorytm nasz działa na jednej, jednoprocesorowej maszynie, dodaje on kolejne elementy ciągu aż dojdzie do końca. Zakładamy, że dodanie dwóch liczb naturalnych jest stałe czasowo (zajmuje jakiś czas C).

Wtedy, jeśli jako dane wejściowe damy ciąg 100 elementowy to czas działania algorymu będzie wynosić około 100*C, gdy damy dane dwa razy większe czyli 200 elementów to wtedy czas będzie wynosić około 200*C. Widać więc, że czas zmienia się wprost proporcjonalnie do rozmiaru danych, czyli taki algorytm ma liniową złożoność (O(n)).

Ok powiedzmy że tego sie już dowiedziałem ale jak ja mam obliczyć złożoność dla mojego algorytmu http://www.speedyshare.com/474372402.html a raczej wiem jaka ona jest a mianowicie liniowa ale nie mam pojęcia jak to zapisać aby osoba która będzie to sprawdzała wiedziała jak ja to liczyłem (bo swoją drogą tej liniowej złożoności to ja pewny nie jestem) ? Jest jakiś ogólnie pryjęty sposób obliczania tej złożoności i apisu tych obliczeń?

Edytowane 16 Stycznia 2007 przez sokarsg-1