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) памяти. Одна операция выполняется быстрее, чем в сортировке слиянием.
