Обозначение Big O

Big O дает нам стандартизированную причину оценки эффективности алгоритма через время его выполнения и пространственно-временную сложность. Сложность времени выполнения - это количество итераций, которые требует алгоритм для решения проблемы, а пространство-время - это количество необходимой памяти. В современных вычислениях пространство не является проблемой, поэтому большинство алгоритмов стремятся оптимизировать сложность времени выполнения.

При определении большого О алгоритма мы формулируем его как приближение и всегда ориентируемся на наихудший сценарий. На следующем графике показаны наиболее распространенные типы Big O.

Постоянное время O (1): золотой стандарт, новые данные не увеличивают время выполнения. Это видно в алгоритмах, использующих математические операции. Другие примеры включают:

  • Доступ к индексу массива (int a = ARR [5];)
  • Вставка узла в связанный список
  • Толкать и хлопать по стеку
  • Вставка и удаление из очереди
  • Поиск родителя или левого / правого дочернего элемента узла в дереве, хранящемся в массиве
  • Переход к следующему / предыдущему элементу в двусвязном списке

Логарифмическое время O (logn): новые данные медленно увеличивают время выполнения. Обычно это наблюдается в алгоритмах поиска, где наборы данных часто сокращаются пополам с каждой итерацией.

  • Бинарный поиск
  • Поиск наибольшего / наименьшего числа в двоичном дереве поиска
  • Определенные алгоритмы «разделяй и властвуй», основанные на линейной функциональности

Линейное время O (n): время выполнения линейно увеличивается с новыми данными. Обычно это означает, что для решения проблемы требуется одна итерация всего набора данных. Примеры включают:

  • Обход массива
  • Обход связанного списка
  • Линейный поиск
  • Удаление определенного элемента в связанном списке (не отсортировано)
  • Сравнение двух строк

Логлинейный O (n log n): время выполнения логарифмически увеличивается с новыми данными. Это часто наблюдается в таких алгоритмах сортировки, как «разделяй и властвуй»:

  • Сортировка слиянием
  • Сортировка кучи
  • Быстрая сортировка

Полиномиальный O (n²): время выполнения быстро увеличивается с новыми данными. Это часто наблюдается во вложенных циклах и основных алгоритмах сортировки, например:

  • Пузырьковая сортировка
  • Вставка сортировки
  • Выбор Сортировка

Экспоненциальное время O (2 ^ n): время выполнения увеличивается экспоненциально с новыми данными.

Рекурсия

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

Регистр прерывания: каждой рекурсивной функции требуется регистр прерывания, чтобы функция могла вернуться, иначе вы получите ошибку переполнения стека.

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

Хорошие варианты использования рекурсии:

Обход дерева и графа

  • Поиск в глубину (дерево)
  • Поиск в ширину
  • Найдите мин. / Макс. В BST

Алгоритмы сортировки

  • Быстрый
  • Объединить
  • Куча

Проблемы, в которых обдумывание итеративного решения кажется слишком сложным

  • Башни Ханоя
  • Выбраться из лабиринта
  • Перестановка строк / Анаграмма

Структуры данных

Массивы

Требуют непрерывного хранилища памяти и индексируются на основе, что делает случайный поиск чрезвычайно быстрым. Большинство языков выделяют дополнительное пространство для массивов, что делает вставку и удаление из хвоста массива эффективными. Вставка или удаление спереди или посередине обходится дорого, потому что массив должен скопировать себя и найти другое место в памяти, в котором есть требуемые блоки памяти.

Связанный список

Не требует непрерывной памяти. Каждый узел содержит указатель на другой узел. Односвязный список содержит только указатель на следующий узел, а двусвязный список также содержит указатель на предыдущий узел. Как правило, связанные списки более эффективны, чем массивы для вставки и удаления в начале или в конце, но не обеспечивают эффективного поиска. По этой причине связанный список является предпочтительной структурой данных для стеков и очередей.

Боковая панель - Местоположение кеша

В современных вычислениях массивы обычно работают лучше, чем связанные списки из-за расположения кеша. У ЦП есть небольшие кеши, в которых хранятся недавно полученные данные из ОЗУ. Сохраняются не только запрошенные данные, но и близлежащие данные. Это хорошо работает для массивов из-за требований к непрерывной памяти, но не для связанных списков.

Хеш-карта

Это отличная структура данных, когда поиск данных должен быть удобочитаемым и принимает форму пар ключ / значение. Карты хеширования могут использовать комбинацию массивов и связанных списков для хранения своих данных. Но перед этим они используют сложные алгоритмы хеширования, которые отображают читаемый человеком ключ в индекс массива. Враг хеш-карт - коллизия. Конфликт - это когда два разных ключа хешируются, но возвращают один и тот же индекс. Для обработки повторяющихся ключей хеш-карты могут использовать либо отдельную цепочку, либо открытую адресацию.

Раздельная цепочка - это когда другой массив или связанный список сохраняется в индексе и вставляются новые пары ключ / значение.

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

Куча

Стек - это структура данных, которая соответствует модели «последний пришел - первым ушел» (LIFO). Стеки можно рассматривать как вертикальную структуру данных. Представьте себе стопку грязной посуды: последняя добавленная тарелка будет первой, которую нужно очистить. Стеки хранят ссылку на вершину и реализуют функции push и pop.

Очередь

Очередь - это структура данных, которая соответствует модели «первым пришел - первым ушел» (FIFO). Очереди похожи на очереди. Первый, кто встанет в очередь, будет первым, кому помогли. Очереди хранят ссылки на начало и конец и реализуют функции постановки в очередь и удаления из очереди.

Сортировка

Сортировка слиянием

Требуется создание вспомогательного метода, который объединяет два отсортированных массива в один отсортированный массив. Работает, потому что отсортирован массив из 1 или без значений. Итак, разбейте массив на массивы длиной 0 или 1, а затем объедините их обратно.

Быстрая сортировка

Требуется создание вспомогательного метода pivot. Метод сортирует все значения меньше него влево и все значения больше вправо. Он возвращает его index. Рекурсивно просматривайте список с меньшим и меньшим массивом, находя каждую точку поворота, пока не дойдете до массива из 1 значения.

Searching

Поиск в ширину

Используйте очередь для хранения всех дочерних узлов узла.

Предварительный заказ поиска в глубину

Сначала распечатайте узел, затем пройдите по дереву, корневой узел должен быть первым

Inorder Depth First Search (поиск в глубину)

Пройдите шаг, распечатайте узел, корневой узел должен быть посередине

Размещать заказ в глубину поиска

Обойдите все дерево, затем распечатайте узел, корневой узел должен быть последним

Бинарный поиск

Работает с отсортированными массивами, находя среднюю точку и проверяя, совпадает ли значение с этим разделом массива. Если он больше средней точки, переместите левую границу вправо, а если она меньше средней точки, переместите правую границу влево.

Общие подходы к решению проблем

Разделяй и властвуй (рекурсия)

Алгоритм «разделяй и властвуй» работает путем рекурсивного разбиения проблемы на две или более подзадач одного и того же или родственного типа, пока они не станут достаточно простыми для непосредственного решения. Затем решения подзадач объединяются, чтобы получить решение исходной проблемы.

Примеры вопросов

  • Большинство алгоритмов сортировки
  • Большинство поисковых алгоритмов
  • Найдите количество оборотов в массиве с круговой сортировкой
  • Найдите максимальное количество шагов, необходимых для достижения конца матрицы
  • Найдите максимальную высоту BST

Раздвижное окно

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

Примеры вопросов

  • Найдите наибольшую сумму последовательных значений «x» в массиве (фиксированное окно)
  • Для строки S и строки T найдите минимальное окно в S, которое будет содержать все символы из T со сложностью O (n).
  • Найти все анаграммы в строке
  • Найдите самую длинную подстроку без повторяющихся символов
  • Найдите максимальную прибыль при покупке и продаже акций

Частотомер

Используйте хэш-карту для сбора значений для последующего быстрого сравнения. Помогает избежать необходимости использовать вложенный цикл. Частотомеры часто можно использовать вместе с шаблоном скользящего окна.

Примеры вопросов

  • Учитывая 2 массива, встречается ли какое-либо значение в массиве 1 в массиве 2?
  • Учитывая 2 массива, содержит ли второй массив все квадраты значений первого?
  • Для данной строки найдите префикс с наибольшей частотой. Если два префикса имеют одинаковую частоту, рассмотрим префикс максимальной длины.
  • Для несортированного массива задача состоит в том, чтобы найти минимальную разницу между любыми парами.

Два указателя

Используйте два указателя для перемещения по двум массивам или строкам. Проблема каждого вопроса будет указывать, когда переместить указатель. Такой подход может помочь уменьшить O (n²) до O (n).

Примеры вопросов

  • Объединить два отсортированных массива в один отсортированный массив
  • Найдите минимальную абсолютную разницу между 3 отсортированными массивами
  • Учитывая 2 отсортированных массива, найдите все элементы, которые встречаются в обоих массивах.
  • Удалить дубликаты из отсортированного массива