worzenie jakiegokolwiek algorytmu czy programu rozwi▒zuj▒cego jaki╢ problem wi▒┐e siΩ bardzo ╢ci╢le z pojΩciem z│o┐ono╢ci obliczeniowej. W tek╢cie tym postaram siΩ przybli┐yµ bardzo skr≤towo to zagadnienie.
worzenie jakiegokolwiek algorytmu czy programu rozwi▒zuj▒cego jaki╢ problem wi▒┐e siΩ bardzo ╢ci╢le z pojΩciem z│o┐ono╢ci obliczeniowej. W tek╢cie tym postaram siΩ przybli┐yµ bardzo skr≤towo to zagadnienie.
Na pocz▒tek - czym w og≤le jest z│o┐ono╢µ obliczeniowa? Og≤lnie rzecz bior▒c, jest to ilo╢µ zasob≤w potrzebnych do zrealizowania danego algorytmu. Przez ilo╢µ zasob≤w rozumie siΩ zar≤wno zasoby pamiΩciowe (ile pamiΩci potrzeba dla wykonania algorytmu) jak i obliczeniowe (ile operacji trzeba wykonaµ). Trzeba wyra╝nie zaznaczyµ, ┐e z│o┐ono╢µ obliczeniowa jest bardzo wa┐nym czynnikiem przy wyborze rodzaju algorytmu. Pocz▒tkuj▒cym "komputerowcom" wydaje siΩ, ┐e dzisiejsze komputery mog▒ wszystko, a zabieganie o konstruowanie szybszych program≤w jest jedynie domen▒ nauczycieli, wyk│adowc≤w, maniak≤w matematycznych i ludzi niepraktycznych. Ten pogl▒d jest b│Ωdny! Mo┐na nawet pokusiµ siΩ o stwierdzenie, ┐e programowanie opiera siΩ na szukaniu rozwi▒za± szybszych, zajmuj▒cych mniej pamiΩci. ZapamiΩtaj: ka┐dy komputer mo┐na "zatkaµ", niezale┐nie, czy na p│ycie masz 286 czy Pentium IV. Ma│o tego, jest to banalnie proste!
Od czego zale┐y z│o┐ono╢µ obliczeniowa? Ka┐dy algorytm ma okre╢lon▒ dla siebie z│o┐ono╢µ obliczeniow▒, najczΩ╢ciej w postaci funkcji np. o(n). "o()" to symbole u┐ywane umownie do oznaczania z│o┐ono╢ci, a "n" to ilo╢µ danych wej╢ciowych (np. ilo╢µ element≤w do posortowania). Rzadko kiedy spotyka siΩ sytuacjΩ podstawienia warto╢ci za "n", gdy┐ taka funkcja ma raczej charakter maj▒cy przybli┐yµ z│o┐ono╢µ funkcji, a nie s│u┐yµ do liczenia konkretnych przypadk≤w.
Jednak dobrze wiadomo, ┐e ka┐de dwa komputery r≤┐ni▒ siΩ parametrami, a co idzie za tym - wydajno╢ci▒. Nie mo┐na wiΩc okre╢laµ z│o┐ono╢ci algorytmu na podstawie np. ilo╢ci sekund, instrukcji procesora czy bajt≤w pamiΩci niezbΩdnych do realizacji algorytmu. Z tego powodu za pojedyncze kroki programu przyjmuje siΩ takie instrukcje, kt≤rych ilo╢µ wyst▒pie± jest ╢ci╢le zale┐na od danych wej╢ciowych. Na przyk│ad, w przypadku algorytm≤w sortuj▒cych za wielko╢µ danych wej╢ciowych przyjmuje siΩ ilo╢µ element≤w do posortowania, a za operacje decyduj▒ce o z│o┐ono╢ci algorytmu - ilo╢µ por≤wna± i przesuniΩµ. Na pierwszy rzut oka trudno uwierzyµ, ┐e takie postΩpowanie ma odzwierciedlenie w praktyce, ale - uwierz mi - tak jest!
Przy omawianiu zagadnienia z│o┐ono╢ci obliczeniowej nie mo┐na pomin▒µ jeszcze jednego aspektu. Dane wej╢ciowe bowiem mog▒ byµ korzystne (tzn. algorytm bΩdzie je przetwarza│ du┐o szybciej, ni┐ by to wynika│o z jego z│o┐ono╢ci, losowe (czyli takie, z jakimi mamy najczΩ╢ciej do czynienia - aczkolwiek nie we wszystkich przypadkach) oraz "z│o╢liwe". Te ostatnie s▒ tak dobrane, ┐e przysparzaj▒ algorytmowi bardzo du┐o pracy, czΩsto demaskuj▒c jego wady. CzΩsto w specyfikacjach algorytm≤w podaje siΩ wiΩc informacje o z│o┐ono╢ciach w przypadkach optymistycznym i pesymistycznym.
A teraz przyszed│ czas na poznanie kilku najwa┐niejszych z│o┐ono╢ci obliczeniowych, kt≤re mo┐na w praktyce spotkaµ szczeg≤lnie czΩsto:
