1. Понятие алгоритмической сложности

Алгоритмическая сложность – функция зависимости объема работы, которая выполняется некоторым алгоритмом, от размера входных данных. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Примеры

Сложность	Название	Применение
О (с)	фиксированная	Вернуть первый элемент списка. для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
О (log n)	логарифмическая	Найти элемент в отсортированном списке (бинарный поиск). Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива - там его точно нет. Если же меньше, то наоборот - отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
О (n)	линейная	Найти в списке элемент с максимальным значением в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
О (n log n)	линейно-логарифмическая	Сортировка списка
О (n^2)	квадратичная	Алгоритм сортировки вставками
О (n^3)	кубическая	Перемножение двух матриц n на n
О (2^n)	экспоненциальная	Решение задачи коммивояжёра с помощью динамического программирования (разбиение задач на более простые подзадачи) Решение задачи о порядке перемножения матриц с помощью полного перебора

2. Сравнить структуры данных массив и список

Структура данных - это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Массив – структура данных, хранящая набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона. Одномерный массив – фиксированное кол-во элементов одного и того же типа, объединенных одним именем.

Динамический массив – массив, размер которого может изменяться во время исполнения программы. Возможность изменения размера отличает динамический массив от статического, размер которого задаётся на момент компиляции программы.

Список - это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляры значений, находящихся в списке, называются элементами списка, если значение встречается несколько раз, каждое вхождение считается отдельным элементом. Реализовываются, как правило, через связные списки.

Связный список – динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки на следующий и/или предыдущий узел списка.

Виды связных списков:

 линейный однонаправленный (односвязный) список, основные операции: инициализация списка, проверка списка на пустоту, добавление узла в список, удаление узла из списка, удаление корня списка, вывод элементов списка, взаимообмен двух узлов списка;

 двунаправленный связный список (те же самые операции);

Структура	Достоинства	Недостатки
Массив	- лёгкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим) - одинаковое время доступа ко всем элементам - малый размер элементов: они состоят только из информационного поля - Сложность времени O (1) - фиксированная	- для статического массива - отсутствие динамики, невозможность удаления или добавления элемента без сдвига других. - для динамического и/или гетерогенного массива - более низкое быстродействие - при работе с массивом с указателями и при отсутствии дополнительных средств контроля - угроза выхода за границы массива и повреждения данных - вероятность потери или нехватки памяти
Связный список	- эффективное (за константное время) добавление и удаление элементов - размер ограничен только объёмом памяти компьютера и разрядностью указателей - динамическое добавление и удаление элементов	- сложность прямого доступа к элементу, а именно определения физического адреса по его индексу (порядковому номеру) в списке - на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память - некоторые операции со списками медленнее, чем с массивами, так как к произвольному элементу списка можно обратиться, только пройдя все предшествующие ему элементы - соседние элементы списка могут быть распределены в памяти нелокально, что снизит эффективность кэширования данных в процессоре - над связными списками гораздо труднее производить параллельные векторные операции, такие, как вычисление суммы - Сложность времени O (n) - линейная