Jak ocenić złożoność obliczeniową algorytmu? - 2h

Teoria obliczeń

Teoria obliczeń to dział informatyki. Jedną z gałęzi tego działu jest teoria złożoności obliczeniowej. W uproszczeniu można powiedzieć, że zajmuje się ona oszacowaniem wydajności czasowej i pamięciowej algorytmów. Teoria złożoności obliczeniowej bazuje na wielu modelach, które służą do łatwego porównywania algorytmów.

Przykład wyznaczania złożoności obliczeniowejń

Załóżmy że chcemy policzyć sumę elementów tablicy. Może nam w tym pomóc następujący algorytm:

public int sum(int[] numbers) { int sum = 0; for (int number : numbers) { sum += number; } return sum; }

Ile mamy w nim operacji? int sum = 0;, przypisanie to jedna operacja. Następnie mamy pętlę for. Jej ciało zawiera jedną operację. Sama pętla wykona się dokładnie tyle razy ile jest elementów tablicy numbers. Liczbę tych elementów określmy jako n. Na końcu mamy instrukcję return sum;. Jest to ostatnia operacja.
Dodając te operacje do siebie otrzymujemy wzór:
f(n)=1+n+1=n+2
Zatem złożoność naszego algorytmu opisana jest przez funkcję f(n) = n + 2.
Złożoność obliczeniową określamy jako funkcję danych wejściowych algorytmu. Wyznacza się ją jak opisałem w poprzednim punkcie – licząc operacje. O ile dla naukowców znalezienie dokładnej funkcji może być bardzo istotne, to w praktyce wystarczą jej oszacowania. Takie oszacowania to notacja Ο (dużego O), notacja Ω (omega) i notacja Θ (theta).

Notacja Ο (dużego O)

Notacja ta zakłada, że istnieje funkcja g(n), dla której spełniona jest poniższa własność:
∀n⩾n0:f(n)⩽c∗g(n)
Własność ta oznacza, że wynik funkcji g(n) pomnożony przez jakąś stałą c będzie większy bądź równy wynikowi funkcji f(n). Własność ta jest spełniona dla wszystkich n, które będą większe od n0.

Notacja Ο jest oszacowaniem z góry. Zatem można powiedzieć, że jeśli algorytm ma złożoność Ο(n^2) to ma także złożoność Ο(n^3) czy nawet Ο(n!). Jednak Ο(n^2) może być najlepszym oszacowaniem złożoności danego algorytmu.

Z racji tego, że jest to oszacowanie pomijamy w nim wszelkiego rodzaju stałe. Zatem Ο(2n + 123), Ο(2n) i Ο(n) to ta sama złożoność obliczeniowa. Stałe te i tak nie mają znaczenia przy odpowiednio dużych wartościach n.

O(1)

Ο(n)

Złożoność liniowa. Jest to specyficzny przypadek złożoności wielomianowej. Czas rozwiązania problemu jest wprost proporcjonalny do wielkości danych wejściowych. Przykład problemu, dla którego istnieje algorytm Ο(n):
Na wejściu programu jest tablica liczb o długości N. Znajdź sumę wszystkich liczb w tablicy wejściowej.

Ο(log(n))

Złożoność logarytmiczna, czas rozwiązania zależy od wyniku logarytmu3 z wielkości danych wejściowych. Przykład problemu, dla którego istnieje algorytm Ο(log(n)):
Na wejściu programu jest posortowana tablica liczb o długości N. Sprawdź czy liczba x istnieje w tablicy wejściowej.
To popularny algorytm przeszukiwania binarnego. Jego nazwa pochodzi od tego, że przy każdej iteracji algorytmu dzielimy przeszukiwany zbiór na dwie równe4 części. Algorytmy, które dzielą w ten sposób problem na mniejsze problemy przeważnie są zależne od logarytmu wielkości danych wejściowych.

Warto podkreślić praktyczne zastosowanie łączenia zdań logicznych poprzez spójniki logiczne w zdania złożone. Dzięki temu możemy pisać kody źródłowe, które są krótsze i bardziej zwięzłe, gdyż wiele instrukcji warunkowych można zastąpić jedną.

Realizując ćwiczenia i zadania polegające na stworzeniu kodu źródłowego o określonym działaniu, warto podkreślić, by przed przystąpieniem do pisania kodu źródłowego pamiętać o wcześniejszych etapach rozwiązywania problemów z wykorzystaniem komputera – na przykład sformułowaniu algorytmu.

Wykorzystując zmienne typu string w języku C++, do kodu źródłowego dodaje się dyrektywę #include . Warto podkreślić, że string i iostream nie są jedynymi bibliotekami, z jakich można korzystać w tym języku. Biblioteki znacznie zwiększają możliwości języka. Można to zilustować animacją Podstawowe biblioteki języka C++, dostępną na stronie dlanauczyciela.pl.

 

Zadanie 2 (łatwe)

Przelicz na system dwójkowy podane poniżej liczby dziesiętne:

10(10) =	(2)	.
100(10) =	(2)	.
1000(10) =	(2)	.
10000(10) =	(2)	.
93673(10) =	(2)	.

 

Zadanie 3 (dosyć łatwe)

Ile razy wzrośnie zakres n-bitowych liczb binarnych, gdy liczbę bitów zwiększymy o 1, 2, 3, 4, m bitów? Odpowiedź uzasadnij.

Zadanie 4 (łatwe)

Obliczyć wartość dziesiętną następujących liczb dwójkowych:

11,101(2) =	(10)	.
101,1101(2) =	(10)	.
1101011,11001(2) =	(10)	.

Zadanie 5 (łatwe)

Przeliczyć podane liczby dziesiętne na zapis dwójkowy:

7,6875(10) =	(2)	.
15,84375(10) =	(2)	.
27,8359375(10) =	(2)	.

Zadanie 6 (dosyć łatwe)

Wyznaczyć 100 cyfr ułamkowych dwójkowego rozwinięcia liczby dziesiętnej 0,8₍₁₀₎.

 

Zadanie 7 (dosyć łatwe)

Wyznacz błąd względny i bezwzględny rozwinięcia dwójkowego liczby dziesiętnej 0,2₍₁₀₎ o dokładności 10 binarnych cyfr ułamkowych.