Algorithms and Data Structures Flashcards
Что показывает нотация О-большое?
Такую нотацию используют для указания на сложность алгоритма. О-большое показывает наихудший случай. Например, сложность О(n) говорит о том, что c ростом n - числа элементов для обработки, - число операций в худшем случае вырастет линейно.
Математическое определение:
f(x) = O( g(x) ) если lim( g(x)/f(x) ) = 0 при x -> inf
Используются ли такие формы записи сложности?
О( n*log(n) + 1 )
O( (1/2) * n^2 )
Эти записи математически корректны, но для алгоритмов используются редко.
Алгоритмы обычно принципиально отличаются по сложности. Например О(n^2) для большого n требует на много порядков меньше операций чем O(n!). Таких случаев большинство, константы в них не играют роли, поэтому их обычно опускают.
Констаны важны только для алгоритмов с одинаковой сложностью. Источником констант может быть как сам алгоритм, так и время одной операции (обычно различается между алгоритмами).
Какие структуры данных вам известны?
Массив Ассоциативный массив Хеш таблица Граф Множество
Абстрактные:
Очередь, Стек,
Что такое массив. Какие операции в нём быстрее, какие медленнее? Почему?
Массив - данные, последовательно хранящиеся в памяти.
Позволяет быстро читать данные с любой позиции (засчёт последовательного хранения).
Медленно вставляет элементы, потому что приходится переносить все последующие элементы, а иногда и весь массив целиком, если он больше не помещается на данном участке памяти.
Что такое ассоциативный массив? Какие операции в нём быстрее, какие медленнее? Почему?
Ассоциативный массив - набор пар (значение, ссылка на след. значение).
Позволяет быстро добавлять новые элементы на произвольные позиции (заменяет переписывает ссылки).
Медленнее, чем массив, читает элементы с произвольных позиций, потому что вынужден последовательно идти по ссылкам от одного элемента к другому.
Заметка: АМ бывают однонаправленными, двунаправленными, круговыми.
Выбирая между массивом и ассоциативным массивом, что ты выберешь для реализации стека? Для очереди? Выбор обоснуй.
Для реализации стека может хорошо подойти массив. Он быстро добавляет/извлекает последний элемент. Размер стека обычно ограничен, а потому известен заранее, что хорошо подходит для массивов.
Для очередей скорее подойдет ассоциативный массив, так как он позволяет быстро удалять первый элемент.
Что такое хеш-таблица? Какие операции в ней быстрее, какие медленнее? Почему?
Неупорядоченный набор пар [ключ, значение].
Поиск значения по ключу происходит за константное время О(1).
Для этого используется хеш-функция, которая по ключу восстанавливает адрес в памяти, где лежит значение.
Что такое граф? Какие виды графов тебе известны?
Граф - это абстрактное представление системы связанных объектов.
Виды графов
- направленный/ненаправленный
- циклический/ациклический
- взвешенный
- дерево (бинарное, тернарное, …, куча )
Как работает бинарный поиск? Какие у него предварительные требования к данным? Какая у него сложность?
Бинарный поиск производится отсортированном массиве.
- Берём элемент из середины массива
- Сравниваем с целевым
- Если совпали - успех. Если целевой больше, то начинаем с 1. для массива справа от середины массива, если меньше - слева.
Сложность O( log(n) )
Какие алгоритмы сортировок вам известны? Какие у них сложности по операциям и вспомогательным данным?
Быстрая сортировка: О( nlog(n) ) и О(n)
Сортировка слиянием: О( nlog(n) ) и О(n)
Сортировка вставками: О( n^2 ) и О(1)
Сортировка выбором: О( n^2 ) и О(1)
Сортировка пузырьком: О( n^2 ) и О(1)
Как и работает сортировка пузырьком? Какая у неё средняя сложность?
Раз за разом проходим по массиву, меняя порядок соседних элементов, если он не верный.
Средняя сложность - O(n^2).
Как работает сортировка вставками? Какая у неё средняя сложность?
Берём элементы по одному и вставляем в нужное место среди уже отсортированных элементов в начале массива.
Средняя сложность - O(n^2).
Как работает сортировка выбором? Какая у неё средняя сложность?
- Находим номер минимального значения в списке.
- Производим обмен этого значения со значением первой неотсортированной позиции.
- Теперь сортируем неотсортированный хвост.
Как работает сортировка слиянием? Какая у неё средняя сложность?
Принцип - “разделяй и властвуй”
- Рекурсивно разбиваем массивы на подмассивы пока они не будут состоять из одного элемента
- Рекурсивно соединяем отсортированные массивы:
- – Берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив
- – Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваем на 1
Средняя сложность - О( n*log(n) ), но требует O(n) доп. памяти и по сравнению с быстрой сортировкой имеет большую константу времени одной операции.
Как работает быстрая сортировка? Какая у неё средняя сложность?
Принцип - “разделяй и властвуй”
- Случайным образом выбираем опорный элемент
- Справа от опорного помещаем элементы, которые больше него, слева - меньше. Сложность - О(n)
- Рекурсивно сортируем массивы справа и слева от опорного - О( log(n) )
Средняя сложность - О( n*log(n) ). Худшая - О(n^2), но встречается очень редко. Требует O(n) памяти. Одна операция выполняется быстрее, чем в сортировке слиянием.
Как работает поиск в ширину? Что он позволяет определить? Какая у него сложность?
Это алгоритм на графах, позволяет определить, достижима ли целевая вершина и сколько рёбер до неё нужно пройти.
Шаг алгоритма
- Проверяем вершины из списка для проверки;
- Если проверяемая вершина не является целевой, добавляем её соседей в список для проверки;
Сложность - O( |V| + |E| ). По памяти - O( |V| )
Как работает алгоритм Дейкстры?
Что он позволяет определить?
Какие ограничения на входные данные?
Какая сложность?
Алгоритм Дейкстры позволяет определить, достижима ли определённая вершина и даёт наиболее дешевый путь до неё.
Применим для взвешенных направленных ациклических графов с неотрицательными весами.
Данные используемые в алгоритме
(Далее КР - это кратчайшее расстояние из самой первой вершины)
1. Таблица [узел, КР]
2. Таблица [узел, родитель с КР]
Шаг алгоритма
- Считаем расстояния из текущей вершины до соседей. Для этого складываем КР до текущей вершины с расстоянием до соседа.
- Если расстояние до соседа из текущей вершины ближе, чем его текущее КР, обновляем ему КР и родителем ставим текущую вершину.
- Проверяем все записанные вершины и переходим в следующую вершину с кратчайшим расстоянием до неё.
- для первой вершины КР = 0, нет родителя
- *для любой ещё не проверенной вершины, КР = inf
Как ты понимаешь определение NP-полной задачи?
Задача, для решения которой потребуется в худшем случае перебор всех возможных решений.
Что такое жадные алгоритмы?
Это алгоритмы, которые локально оптимальны - в каждой итерации выбирается наилучшее решение в рамках текущей итерации.
