From bc6fa2f8d7967acd859c0f660cad81199e53b0fb Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 19 May 2022 14:12:12 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B8?=
 =?UTF-8?q?=D0=B5=20=D0=BE=D1=82=D1=87=D1=91=D1=82=D0=BE=D0=B2=20=D0=BF?=
 =?UTF-8?q?=D0=BE=20=D0=BF=D0=B5=D1=80=D0=B2=D1=8B=D0=BC=20=D1=82=D1=80?=
 =?UTF-8?q?=D1=91=D0=BC=20=D0=BB=D0=B0=D0=B1=D0=B0=D0=BC?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 reports/lab1/lab1.tex | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
 create mode 100644 reports/lab1/lab1.tex

(limited to 'reports/lab1/lab1.tex')

diff --git a/reports/lab1/lab1.tex b/reports/lab1/lab1.tex
new file mode 100644
index 0000000..ad35f80
--- /dev/null
+++ b/reports/lab1/lab1.tex
@@ -0,0 +1,37 @@
+\documentclass[spec, och, labwork]{SCWorks}
+\usepackage{preamble}
+
+\begin{document}
+\include{titlepage.tex}
+
+\section*{Описание работы алгоритма}
+
+На $i$-м шаге выполнения алгоритма необходимо найти некоторый $k$-й наименьший
+элемент, где $i < k \leq n$, $n$ "--- размер массива. После того, как $k$-й
+элемент был найден необходимо поменять его местами с $i$-м элементом.
+
+Данный алгоритм необходимо повторить для каждого элемента массива. Таким образом
+будет получен массив, отсортированный по неубыванию.
+
+\subsection*{Оценка сложности}
+
+Нахождение минимального элемента в массиве требует проверки $n$ элементов
+($n - 1$ сравнений). Нахождение следующего минимального элемента потребует
+проверки $n - 1$ элементов ($n - 2$ сравнений). Таким образом, всего будет
+произведено следующее количество сравнений:
+\[ (n - 1) + (n - 2) + \ldots + 1 = \sum_{i = 1}^{n - 1} i \]
+
+Преобразуя данное выражение, получим
+\begin{equation*}
+    \sum_{i = 1}^{n - 1} i = \frac{(n - 1) + 1}{2} (n - 1) =
+    \frac{1}{2} n (n - 1) = \frac{1}{2} (n^2 - n)
+\end{equation*}
+
+Таким образом получаем, что алгоритм сортировки с помощью прямого выбора имеет
+алгоритмическую сложность $O(n^2)$ в среднем, лучшем и худшем случаях.
+
+\subsection*{Реализация на языке C++}
+
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../../straight-selection.cpp}
+
+\end{document}
-- 
cgit v1.2.3