147 lines
7.1 KiB
TeX
147 lines
7.1 KiB
TeX
%! TEX root = ../main.tex
|
|
|
|
\section{Wprowadzenie}
|
|
Tworząc oprogramowanie jednym z aspektów, na które powinniśmy zwrócić szczególną uwagę jest wydajność - zarówno czasowa,
|
|
jak i pamięciowa. Wydajność czasową rozumiemy oczywiscie przez czas, w którym wykonuje się nasz program, a przez
|
|
pamięciową ilość pamięci operacyjnej, którą potrzebuje program do działania.
|
|
|
|
Wydajność czasowa nie może być rozumiana jako ilość sekund potrzebna do wykonania danego programu. Absolutny wymiar czasu
|
|
- podany w sekundach - jest zależny od wielu czynników, w tym szybkości komputera czy zajętości jego zasobów. Dlatego
|
|
w celu badania wydajnosci czasowej programu najczęściej rozpatrujemy liczbę operacji jaką musi wykonać program dla
|
|
pewnych danych. Dlatego w dalszej mówiąc o czasie będziemy się skupiać na liczbie takich kroków.
|
|
|
|
\subsection{Przedstawienie liczby operacji w formie sumy}
|
|
Załóżmy, że mamy pętlę:
|
|
\begin{algorithmic}[1]
|
|
\For{$i = 1 \ldots n$}
|
|
\State \Call{$f$}{$i$}
|
|
\EndFor
|
|
\end{algorithmic}
|
|
|
|
Wiemy, że czas działania (rozumiany jako liczba operacji) funkcji $f$ możemy wyznaczyć za pomocą funkcji $T_f(n)$ (ta
|
|
konwencja oznaczania będzie utrzymana przez dalsze rozdziały). Pętla wywołuję funkcję $f$ dla każdego $i$ od 1 do $n$,
|
|
zatem czas działania funkcji możemy przedstawić następująco:
|
|
|
|
\begin{equation}
|
|
T = T_f(1) + T_f(2) + T_f(3) + \cdots + T_f(n) = \sum_{i = 1}^{n} T_f(i) \label{eq:1-intro:loop-to-sum}
|
|
\end{equation}
|
|
|
|
Weźmy inny program:
|
|
\begin{algorithmic}[1]
|
|
\For{$i = 1; i < n; i \gets 2i$}
|
|
\State \Call{$f$}{$i$}
|
|
\EndFor
|
|
\end{algorithmic}
|
|
|
|
W tym wypadku, kolejne wartości $i$ będą kolejnymi potęgami 2, zatem czas jaki przeznaczymy na wykonanie tej pętli
|
|
zapiszemy jako:
|
|
\begin{equation*}
|
|
T = T_f(1) + T_f(2) + T_f(4) + T_f(8) + \cdots
|
|
\end{equation*}
|
|
|
|
Na pierwszy rzut oka ciężko zamienić ten program na matematyczną sumę. Jak jednak zostało zauważone, kolejne wartości
|
|
$i$ są kolejnymi potęgami 2. Załóżmy zatem, że $l$ jest licznikiem wykonań pętli, tj. reprezentuje ilość już wykonanych
|
|
iteracji. W takim wypadku moglibyśmy powiedzieć, że:
|
|
\begin{equation*}
|
|
i = 2^l
|
|
\end{equation*}
|
|
|
|
czyli warunek $i < n$ byłby spełniony wtedy i tylko wtedy, gdy:
|
|
\begin{equation*}
|
|
2^l < n \iff l < \log_2 n
|
|
\end{equation*}
|
|
|
|
Ponieważ $l$ z założenia jest licznikiem pętli - to wiemy, że pętla wykona się nie więcej niż $\log_2 n$ razy.
|
|
Łącząc te 2 informacje uzyskamy taki wzór na czas:
|
|
\begin{equation*}
|
|
T = T_f(1) + T_f(2^1) + T_f(2^2) + T_f(2^3) + \cdots = \sum_{i=0}^{\log_2 n} T_f(2^i)
|
|
\end{equation*}
|
|
|
|
Oczywiście nic nie stoi na przeszkodzie, aby rozważać pętle w pętlach:
|
|
\begin{program}[H]
|
|
\begin{algorithmic}[1]
|
|
\For{$i = 1\ldots n$}
|
|
\For{$j = 1\ldots n$}
|
|
\State \Call{$f$}{$i, j$}
|
|
\EndFor
|
|
\EndFor
|
|
\end{algorithmic}
|
|
\end{program}
|
|
Zgodnie z wcześniejszymi ustaleniami wewnętrzna pętla wykona sie przez czas $T_w = \sum_{j = 1}^n T_f(i, j)$.
|
|
Zewnętrzną rozpatrzymy analogicznie, uzyskując:
|
|
\begin{equation}
|
|
T = \sum_{i=1}^n T_w = \sum_{i=1}^n \sum_{j = 1}^n T_f(i, j)
|
|
\end{equation}
|
|
|
|
Załóżmy, że mamy program który sumuje nam wszystkie liczby od 1 do $n$, program prezentuje się następująco:
|
|
\begin{program}[H]
|
|
\begin{algorithmic}[1]
|
|
\Require
|
|
\Statex $n$ - liczba naturalna \label{line:1-intro:n}
|
|
\Statex
|
|
|
|
\State $S \gets 0$ \Comment{$S \gets 0$ oznacza, że do zmiennej $S$ przypisujemy wartość $0$} \label{line:1-intro:S}
|
|
\For{$i = 1 \ldots n$}
|
|
\State $S \gets S + i$ \label{line:1-intro:loop}
|
|
\EndFor
|
|
\end{algorithmic}
|
|
\end{program}
|
|
|
|
Linia \ref{line:1-intro:S} to jedna operacja przypisania, wykonująca się w czasie $T_\gets$, a w pętli wykonujemy
|
|
operacje przpisania i dodania o łącznym czasie $T_\gets + T_+$. Ponieważ w komputerach operujemy zwykle na liczbach
|
|
o stałym rozmiarze to możemy założyć, że oba te czasy są niezależne od zmiennej $i$. Zgodnie z równaniem
|
|
\ref{eq:1-intro:loop-to-sum} możemy zapisac, że łączny czas wykonania tego programu wynosi
|
|
\begin{equation*}
|
|
T = T_\gets + \sum_{i = 1}^{n}(T_\gets + T_+)
|
|
\end{equation*}
|
|
|
|
Ponieważ $T_\gets + T_+$ jest stałe (tj. nie zależy od zmiennej $i$) to możemy wyciągnąć to wyrażenie przed znak sumy:
|
|
\begin{equation*}
|
|
T = T_\gets + (T_\gets + T_+)\sum_{i = 1}^{n} 1
|
|
\end{equation*}
|
|
|
|
A ponieważ $\sum_{i = 1}^n 1 = n$ (patrz \ref{eqn:sum:1} z strony \pageref{appendix:sum-formulas}), to
|
|
całe równanie możemy sprowadzić do:
|
|
\begin{equation}
|
|
T = T_\gets + (T_\gets + T_+)n = (n+1)T_\gets + nT_+
|
|
\end{equation}
|
|
|
|
Program wykona zatem $n+1$ operacji przypisania i $n$ operacji dodawania.
|
|
|
|
\subsection{Asymptotyczne tempo wzrostu - notacja dużego $O$}
|
|
Jak widac po powyższych przykładach, nawet dla prostych programów ustalenie dokładnej liczby kroków może być uciążliwe
|
|
i czasochłonne. Biorąc pod uwagę, że i tak nie jesteśmy zainteresowani czasem w sekundach często bardziej interesuje
|
|
nas ogólny pogląd na zachowanie programu. Wiemy np, że każda (rosnąca) funkcja liniowa rośnie szybciej od funkcji
|
|
stałej - gdzie przez ,,rośnie szybciej'' rozumiemy, że od pewnego momentu wykres funkcji liniowej na pewno znajdzie
|
|
się nad wykresem funkcji stałej (obie są prostymi, w dodatku nie równoległymi, więc na pewno się przetną) i tak już
|
|
pozostanie do końca.
|
|
|
|
Udowodnijmy, że żadna funkcja liniowa postaci $a_lx + b_l$ nie będzie rosła szybciej niż jakakolwiek funkcja kwadratowa
|
|
$a_kx^2 + b_kx + c_k$. Na nasze potrzeby potrzebujemy tylko rozważyć funkcje rosnące - ponieważ czas nie płynie do tyłu,
|
|
zatem $a_l, a_k > 0$. Chcąc wyznaczyć, kiedy funkcja liniowa jest większa od kwadratowej musimy rozpatrzyć następującą
|
|
nierówność:
|
|
\begin{equation}
|
|
a_lx + b_l > a_kx^2 b_kx + c_k
|
|
\end{equation}
|
|
|
|
Przenieśmy wszystkie składniki na lewą stronę nierówności:
|
|
\begin{equation*}
|
|
-a_kx^2 a_lx - b_kx + b_l - c_k > 0
|
|
\end{equation*}
|
|
\begin{equation*}
|
|
-a_kx^2 + (a_l - b_k)x + (b_l - c_k) > 0
|
|
\end{equation*}
|
|
|
|
Ponieważ z założenia $a_k > 0$ to parabola ma ramiona skierowane w dół, czyli od pewnego momentu na pewno znajduje się
|
|
poniżej osi \texttt{x}. Zatem nawet przy skrajnie dużej wartości współczynnika $a_l$ (określającego szybkość wzrostu funkcji
|
|
liniowej) oraz jednocześnie skrajnie małej wartości współczynnika $a_k$ funkcja liniowa w pewnym momencie znajdzie sie
|
|
pod funkcją kwadratową. Czyli nawet najszybsza funkcja liniowa rośnie wolniej od najwolniej rosnącej funkcji kwadratowej.
|
|
Jak widać po powyższym, dokładne wartości stałych nie mają w tym wypadku znaczenia. Analogiczny dowód możemy
|
|
przeprowadzić dla dowolnej innej funkcji wielomianowej, również o wykładniku niebędącym liczbą całkowitą.
|
|
|
|
Jeżeli między funkcjami $f$ i $g$ zachodzi taka zależność, to jest - bez względu na mnożnik, funkcja $f$ rośnie wolniej
|
|
od $g$ - to mówimy, że $f = o(g)$. Formalnie zależność te definiujemy następująco:
|
|
\begin{equation}
|
|
\forall_{c > 0}\exists_{n_0}\forall_{n > n_0} f(n) < c \cdot g(n)
|
|
\end{equation}
|