1. 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.

1. 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(n²)

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(n³), O(n⁴)... noszą nazwę wielomianowych złożoności obliczeniowych.

Złożoność obliczeniowa logarytmiczna - O(log₂n)

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 log₂n)

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(2ⁿ), O(n!)

Złożoność obliczeniową O(2ⁿ) 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 obliczeniowej O()
O(1)
O(log2n)
O(n)
O(nlog2n)
O(n^2)
O(n^3)
O(2^n), O(n!)

3) Korzystaj z oszacowań

• szacuj wstępnie czas wykonania zadania oraz zajętość pamięci, aby odrzucić nierealne rozwiązania

1. 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ę.

1. Nie komplikuj – Podsumowanie
   

1. 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.

2. Prosty kod jest niekiedy bezpieczniejszy, odporniejszy i efektywniejszy niż jego bardziej skomplikowany odpowiednik

3. 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ą

1. 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

2. 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