Badanie złożoności algorytmów cz I 1

BADANIE ZŁOŻONOŚCI ALGORYTMÓW CZĘŚĆ I

Miara sprawności danego algorytmu jest pamięć i czas potrzebny do jego wykonania. Mamy więc złożoność czasowa i pamięciowa.

Niewątpliwie czas obliczeń, a czasami i pamięć zależą od liczby danych wejściowych, głównie jednak zależą od złożoności naszego algorytmu. Sąalgorytmy, których wykonanie na obecnie dostępnych komputerach wymagałoby milionów lat. Takim przykładem jest rozłożenie na czynniki pierwsze liczby 300 cyfrowej — wymagałoby to rzeczywiście kilku milionów lat pracy najszybszych obecnie dostępnych komputerów. Liczba 300 cyfrowa jest do zapisania na odpowiednio długiej wstędze papieru, ale jak wielka to jest liczba zdać sobie można jedynie porównując ją np. z liczbą protonów w całym Wszechświecie — liczba 126 cyfrowa lub liczby mikrosekund od Wielkiego Wybuchu (~15 mld lat) — liczba 24 cyfrowa. Trzeba zatem ulepszać algorytmy —optymalizować ie.

Jedna z głównych metod optymalizacji polega na znajdywaniu wewnątrz pętli takich operacji, które mogą być wykonane poza nimi.

Przykład:

Rozważmy program, w którym pewną listę wartości L (1)...L (N) spełniająca dla I = 1 ...N warunek 0 L (I) < MAK (MAK — pewna liczba) trzeba unormować tak by mieściły się w przedziale od 1 do 100 czyli 0 < L (I) < 100.

Algorytm tego zadania jest prosty. Wystarcza jedna pętla.

Dla I od 1 do N wykonaj:

L (I): = L (I) * 100 / MAX

Czynność dzielenia 100 / MAK jest tu wykonana podczas każde iteracji pętli. Wystarczy wynieść ją przed pętlą: skala: = 100/MAK dla I od 1 do N wykonaj:

L (I): = L (I) * skala

by czas obliczeń skrócić do połowy (zamiast mnożenia i dzielenia tylko mnożenie).

Czasami trzeba dokonać pewnego triku uzyskania warunków dla takiej optymalizacji. Zilustruje to kolejny przykład.

Przykład — wyszukiwanie łiniowe:

Przeszukiwanie listy nie uporządkowanych elementów celem sprawdzenia czy jest na liście interesujący nas element E.

Najprościej, ale nie optymalnie:

Wykonanie dla każdego elementu listy (czyli w pętli):

a.    sprawdzenie czy dany element to E

b.    czy jest to ostatni element listy (koniec listy)

Spełnienie któregokolwiek z warunków oznacza koniec ze skutkiem pozytywnym lub nie. Na pozór obie czynności są nieodzowne i nie da się tu nic wyprowadzić poza pętlę. Ale jest prosta sztuczka polegająca na dodaniu na koniec listy w sposób sztuczny elementu szukanego E. Wtedy wystarczy sprawdzać w pętli tylko jeden warunek, czy dany element to E, jeśli tak — to wyjście, natomiast kontrola czy element znaleziony E był na końcu listy (jest ostatni elementem listy) można przeprowadzić tylko raz w momencie znalezienia E. Jeśli znaleziony element będzie ostatnim elementem listy to znaczy, że nie było go w oryginalnej liście. Jeśli zaś nie jest ostatni a znaleziono go, to znaczy że był w środku. I w ten sposób realizujemy ten algorytm w czasie, co najmniej dwukrotnie mniejszym. Nie wolno tylko zapomnieć o usunięciu sztucznie dodanego elementu z listy.