Ogólne zasady projektowania algorytmów i programowania
Pracuj nad właściwie sformułowanym problemem
Dokładna analiza nawet małego zadania może prowadzić do ogromnych korzyści praktycznych:
skrócenia długości kodu,
czasu programowania,
czasu wykonania programu
Osoba zamawiająca program często próbuje narzucić programiście niewłaściwe rozwiązanie, dlatego analiza postawionego problemu i własny pomysł na jego rozwiązanie są bardzo istotne.
Zbadaj przestrzeń rozwiązań
1) Programista nigdy nie powinien zabierać się do programowania pierwszego pomysłu algorytmu, tylko szukać innych, lepszych rozwiązań. Tworzenie prototypów lub projektów algorytmów pozwala na wybranie najlepszego rozwiązania (inne rozwiązania niekoniecznie są złe jednak dążymy do najlepszego efektu)
2) Problem, który wydaje się trudny, może mieć proste, nieoczekiwane
rozwiązanie. Należy porównywać średnią złożoność obliczeniową* różnych rozwiązań tego samego problemu, co w efekcie będzie prowadziło do przyspieszenia działania programu oraz zwiększenia zakresu danych wejściowych.
Najlepszym przykładem jest wyszukiwanie, gdzie znamy kilka metod, które w trudności implementacji są do siebie zbliżone, a w efektywności znacznie się różnią. (jednak lepsze rozwiązania posiadają czasem pewne ograniczenia na które nie możemy sobie w danym przypadku pozwolić).
* Przez złożoność obliczeniową algorytmów rozumiemy ilość zasobów niezbędnych do wykonania algorytmu. Przez zasoby rozumie się zwykle czas (złożoność czasowa) i zajętość pamięci operacyjnej (złożoność pamięciowa).
Czas działania algorytmu zależy od samego algorytmu oraz od szybkości działania komputera, rodzaju i wielkości danych.
Złożoność obliczeniowa stała - O(1)
Algorytm wykonuje stałą ilość operacji dominujących bez względu na rozmiar danych wejściowych.
Złożoność obliczeniowa liniowa - O(n)
Dla każdej danej algorytm wykonuje stałą ilość operacji dominujących. Czas wykonania jest proporcjonalny do liczby n danych wejściowych.
Złożoność obliczeniowa kwadratowa - O(n2)
Algorytm dla każdej danej wykonuje ilość operacji dominujących proporcjonalną do liczby wszystkich przetwarzanych danych. Czas wykonania jest proporcjonalny do kwadratu liczby Inne złożoności tego typu O(n3), O(n4)... noszą nazwę wielomianowych złożoności obliczeniowych.
Złożoność obliczeniowa logarytmiczna - O(log2n)
W algorytmie zadanie rozmiaru n da się sprowadzić do zadania rozmiaru n/2. Typowym przykładem jest wyszukiwanie binarne w zbiorze uporządkowanym. Sprawdzenie środkowego elementu pozwala określić, w której z dwóch połówek zbioru może znajdować się poszukiwany element.
Złożoność obliczeniowa liniowo logarytmiczna - O(n log2n)
Zadanie rozmiaru n daje się sprowadzić do dwóch podzadań rozmiaru n/2 plus pewna ilość operacji, których liczba jest proporcjonalna do ilości danych n. Tego typu złożoność obliczeniową posiadają dobre algorytmy sortujące
Złożoność obliczeniowa wykładnicza - O(2n), O(n!)
Złożoność obliczeniową O(2n) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdego podzbioru n danych wejściowych.
Złożoność obliczeniową O(n!) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdej permutacji n danych wejściowych.
Złożoność obliczeniowa wykładnicza jest bardzo niekorzystna, ponieważ czas wykonania rośnie szybko wraz ze wzrostem liczby danych wejściowych.
Porównanie klas złożoności obliczeniowych |
||
Klasa złożoności |
Nazwa klasy złożoności |
Cechy algorytmu |
O(1) |
Stała |
działa prawie natychmiast |
O(log2n) |
Logarytmiczna |
niesamowicie szybki |
O(n) |
liniowa |
szybki |
O(nlog2n) |
liniowo-logarytmiczna |
dosyć szybki |
O(n2) |
kwadratowa |
wolny dla dużych n |
O(n3) |
sześcienna |
wolny dla większych n |
O(2n), O(n!) |
wykładnicza |
nierealizowalny dla większych n |
3) Korzystaj z oszacowań
szacuj wstępnie czas wykonania zadania oraz zajętość pamięci, aby odrzucić nierealne rozwiązania
Przyjrzyj się danym
1) Stosuj odpowiednie do zadania struktury danych, uzyskując:
przyspieszenie działania programu,
oszczędność pamięci,
łatwiejszą konserwację w przyszłości
Na przykład przekształć powtarzający się kod w tablicę.
Nie komplikuj - Podsumowanie
Rozwiązuj problemy w tak prosty sposób jak to tylko możliwe, w przypadku gdy lepsze rozwiązanie jest zbędne i osiągnęliśmy wystarczającą efektywność algorytmu oraz zakres jego działania.
Prosty kod jest niekiedy bezpieczniejszy, odporniejszy i efektywniejszy niż jego bardziej skomplikowany odpowiednik
Jeżeli trzeba, idź na ustępstwa
stosuj kompromis między czasem wykonania programu a rozmiarem wymaganej przez ten program pamięci
stosuj kompromis pomiędzy stopniem optymalizacji kodu a jego przejrzystością
Podsumowując, optymalizuj kod (zarówno pod względem czasu wykonania jak i użycia pamięci) tylko wtedy, jeżeli koniecznie trzeba to zrobić; nie optymalizuj za wcześnie
Główna celem projektowania algorytmów jest uzyskanie zadowalającej w danym przypadku efektywności programu, dlatego też staraj się zapewnić najwyższą jakość na najwyższym poziomie:
definicji problemu,
struktury systemu,
stosowanych algorytmów
doborze struktur danych