%! 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}