\Section{Время работы программ}{11 сентября}{Федорова Анна}

\Subsection{Время работы некоторых операций}

При написании программы, если хочется, чтобы она работала быстро, стоит обращать внимание не только на асимптотику, но и избегать использования некоторых операций, которые работают дольше, чем кажется.
\begin{MyList}
  \item Операции библиотеки \t{math.h: sqrt, cos, sin, tg, arctg} и т.д.
    Эти операции раскладывают переданный аргумент в ряд, что происходит не за $\O(1)$.
  \item Взятие числа по модулю, деление с остатком (\t{a / b, a \%{} b});
  \item Обращение к элементу массива по номеру.
  \item \t{Random access} к памяти при больших массивах.
    Существует два способа прохода по массиву: \t{Random access} и \t{Sequential access}, \\
    \parbox{5cm}{\t{Random access}:}     \lstinline!for (int i = 0; i < n; i++) sum += a[p[i]];!, где $p$ -- случайная перестановка\\
    \parbox{5cm}{\t{Sequential access}:} \lstinline!for (int i = 0; i < n; i++) sum += a[i];!\\
    Первый обращается к случайным элементам, а второй пробегает весь массив строго по порядку.
    Если массив не влезает в кеш ($\sim{}4M$), то он хранится в оперативной памяти.
    Когда мы обращаемся к одному из элементов, часть массива (около $2^{12}$ элементов) переносится в кеш,
    где происходит дальшейшая работа с ним. Если мы захотим обратится к элементу, которого в кеше нет, но он находится в оперативной памяти,
    то скопированный в кеш кусок удаляется и записывается следующая часть, где содержится нужный нам элемент.
    Поэтому, когда мы обращаемся к элементам массива в случайном порядке, в худшем случае мы каждый раз будем переносить
    большие куски массива в кеш из оперативной памяти. Это долго. 
    Когда же мы идем по массиву по порядку, то переносить части массива нам придется намного реже.
    Если у нас есть два алгоритма: $T_1 = T_2 = \O (n^2); M_1 = \O (n^2); M_2 = \O (n)$, то второй алгоритм будет работать быстрее для больших значений $n$.
  \item Функции работы с памятью: \t{new}, \t{delete}.
  \item Вызов функций. Для оптимизации можно использовать \t{inline} -- указание оптимизатору,
    что функцию следует попытаться вставить в код.
    %При большом количестве вызовов простая функция сложения с \t{inline} может работать в несколько раз быстрее.
%\begin{MyTabbing} 
%   inline int foo()\{ \\
%   \> foo(); \\
%   \}\\
% \end{MyTabbing}
  \item Ввод и вывод данных. \t{cin/cout}, \t{scanf/printf}... Используйте буфферизированный ввод/вывод через \t{fread/fwrite}.
\end{MyList}

\pagebreak
\Subsection{Оценка количества операций.}

\begin{Thm}$\forall x, y > 0, z > 1: \exists N: \forall n > N: \log^x n < n^y < z^n$\end{Thm}
\begin{proof} 
Пусть $\log n = k$, тогда $\log^x n < n^y \EQ k^x < 2^{ky} = (2^y)^k = z^k \Leftarrow n^y < z^n \quad\blacksquare$\\
Докажем вторую часть исходного неравенства $n^y < z^n\colon n^y < z^n \EQ n < 2^{\frac{1}{y} n \log z}$\\
Пусть $n^\prime = {1 \over y} n \log z$, обозначим $C = {1 \over y} \log z$, пусть $C \le n^\prime$ (возьмём достаточно большое $n$), тогда\\ 
$n^y < z^n\colon n^y < z^n \EQ n < 2^{\frac{1}{y} n \log z} \EQ C\cdot n^\prime < 2^{n^\prime} \EQ (n^\prime)^2 < 2^{n^\prime}$\\

Докажем по индукции: если $n \to 2n : n^2 \to 4n^2 : 2^n \to {2^n} \cdot {2^n}$ (т.е. одно увеличилось в 4 раза, второе в $2^n$ раз)\\
База: для любого значения из интервала $[10..20)$ верно т.к. $20^2 = 400 < 1024 = 2^{10}$.\\
%$\forall n \in [10;20)\colon n^2 < 20^2 = 400$; $2^n \ge 2^{10} = 1024 \EQ n^2 < 2^n$\\
$[10..20) \to [20..40) \to [40..80) \to \dots$\\
\end{proof}

\Section{Структуры данных}{11 сентября}{Федорова Анна}

\Subsection{Массив}

Создать массив целых чисел на 10 элементов: $int a[10]$; индексация начинается с 0, массивы имеют фиксированный размер. \\
Функции:
\begin{MyList}
  \item $a[i]$ -- обратиться к элементу массива с номером $i$
  \item $a[i] = x$ -- присвоить элементу под номером $i$ значение $x$
  \item $find(x)$ -- найти элемент со значением $x$
  \item $add, insert, put, append$ -- добавить элемент
  \item $delete, erase, remove$ -- удалить элемент
\end{MyList}
Последние две команды работают очень долго -- надо найти новый кусок памяти нужного размера, скопировать весь массив туда, удалить старый.

\Subsection{Двусвязный список}

Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки на следующий и на предыдущий элементы. Первый элемент списка ссылается на $NULL$ в качестве своего левого соседа, последний -- на $NULL$, как на правого.\\
Функции:
\begin{MyList}
  \item $add\_front(x), add\_after(node *v, int x), add\_back(x) : \O (1)$ -- добавить элемент (в начало, в середину, в конец)
  \item $del\_front(), del\_after(node *v), del\_back() : \O (1)$ -- удалить элемент (из начала, из середины, из конца)
  \item $find(x) : \O (length)$ -- найти элемент со значением $x$
  \item $get(i) : \O(min(i, length - i))$ -- получить значения элмента с номером $i$
  \item $add(i, x) = get + add\_after$
\end{MyList}
\begin{code} 
struct node {
  node *l, *r;
  int data;
}
struct List {
  node *head, *tail;
  int length;
}
\end{code}
\Subsection{Односвязный список}

Это список, где указатели ссылаются только на одного соседа (либо левого, либо правого, для каждого узла одинаково).
Всем остальным оно не отличается от двусвязного списка.
\begin{code} 
struct node {
  node *next;
  int data;
}
\end{code}

\Subsection{Стек}

Функции:
\begin{MyList}
  \item $pop\_back$ -- удалить с конца
  \item $push\_back$ -- добавить в конец
  \item $back$ -- посмотреть последний элемент
\end{MyList}

\Subsection{Очередь}

Функции:
\begin{MyList}
  \item $pop\_front$ -- удалить из начала
  \item $push\_back$ -- добавить в конец
  \item $front$ -- посмотреть первый элемент
\end{MyList}

\Subsection{Дек}

Функции:
\begin{MyList}
  \item $pop\_back$ -- удалить с конца
  \item $pop\_front$ -- удалить из начала
  \item $push\_back$ -- добавить в конец
  \item $push\_front$ -- добавить в начало
  \item $back$ -- посмотреть последний элемент
  \item $front$ -- посмотреть первый элемент
\end{MyList}
При использовании стека, дека и очереди могут быть проблемы с временем работы, так что лучаше реализовывать их самостоятельно, например, на списках.

\Subsection{Векторы}

Вектор -- динамический массив (array + stack).\\
Функции:
\begin{MyList}
\item $pop\_back$ -- удалить с конца
\item $push\_back$ -- добавить в конец
\item $vect[i]$ -- обращение к элементу с номером $i$
\item $set(i, x)$ -- добавить элемент со значением $x$ после элемента под номером $i$
\end{MyList}
Вместо того, чтобы каждый раз выделять новую память под один элемент, можно один раз увеличить размер вектора в 2 раза, 
когда он весь заполнится элементами, и понадобится новое место, снова увеличим его в 2 раза и т.д. 
В среднем, время работы такого алгоритма будет среднее арифметическое подряд идущих команд $push$.

\Section{Амортизированное время работы}{11 сентября}{Федорова Анна}

\Subsection{Амортизация}

Реальное время работы операции -- $t_i$.\\
Среднее время работы операции -- $\frac{t_i}{n}$.\\
Рассмотрим произвольную функцию $\varphi$ (потенциал). 
\begin{Def}{Амортизированное время работы программы} \\
  $a_i = t_i + \Delta \varphi$, где $\Delta \varphi = \varphi_{i{+}1} - \varphi_i$ (реальное время плюс изменение потенциала).
\end{Def}
Изначально потенциал равен $\varphi_0$, после выполнения $i$-ой операци -- $\varphi_i$, в конце $\varphi_{last}$.
Амортизированное время можно определять с использованием любой потенциальной функции.

Заметим, что $\sum a_i = \sum t_i + (\varphi_{last} - \varphi_0) \SO \mfrac{\sum t_i}{n} \le \max a_i + \mfrac{\varphi_{0} - \varphi_{last}}{n}$.
В амортизационном анализе наша цель -- подобрать $\varphi$ так, чтобы и $\max a_i$, и $\mfrac{\varphi_{0} - \varphi_{last}}{n}$ были не велики.

%Амортизированное время работы -- среднее время за все запросы.\\
%Вычисляется по формуле: $a_i = t_i + \Delta \varphi$ -- время работы $i$-ой операции, $\Delta \varphi = \varphi_{i + 1} - \varphi_i$, где $\varphi_i$ -- потенциал.\\
%Изначально потенциал равен $\varphi_0$, после выполнения $i$-ой операци -- $\varphi_i$\\
%$\sum a_i = \sum t_i + (\varphi_{last} - \varphi_0)$\\
