-
Нотация О большое для оценки сложности алгоритмов
-
Структуры данных и их применение в алгоритмах
-
Некоторые рекомендации для разработки на .NET
При написании алгоритмов нужно учитывать их масштабируемость. Для этих целей используется понятие «О большое», представленное Паулем Бахманном в 1894 году для того, чтобы приблизительно оценивать, как время выполнения алгоритма будет расти при увеличении размеров входных данных.
Пусть f(n) — время выполнения алгоритма, а g(n) - временная сложность, которая проверяется для алгоритма. Тогда f(n)=O(g(n)), если существует константа k (k > 0) и n0, такие, что f(n) <= kg(n) для всех n, начиная с некоторого n0 (n > n0).
Пример.
Пусть f(n)=4n2-8n+17
тогда f(n)=O(n2), поскольку
4n2-8n+17 <= 10n2 при n>2
Говоря о сложности алгоритмов, часто рассматривается наихудшее время работы алгоритма, и для его описания используются следующие О нотации:
O(1) - константная сложность - время выполнения такого алгоритма не зависит от длины исходных данных
O(n) - линейная сложность - время выполнения такого алгоритма, прямо пропорционально длине обрабатываемых исходных данных, т.е. при увеличении размера n в 10 раз, время работы алгоритма возрастет также в 10 раз
O(n2) - квадратичная сложность - время пропорциональное квадрату длины входных данных, т.е. при увеличении размера n в 10 раз, время работы алгоритма возрастет в 102=100 раз.
O(logn) - логарифмическая сложность - время будет расти меньше, в сравнении с линейной сложностью, но быстрее, чем у константной, например, при увеличении размера n в 10 раз, время работы алгоритма возрастет в log210 = 3.32 раза.
O(nlogn) - линейно-логарифмическая сложность - время будет расти быстрее, чем у O(n), но медленнее, чем у O(n2). К примеру, при увеличении размера n в 10 раз, время работы алгоритма возрастет в 10log210 = 10*3.32 = 33.2 раза.
Критерии, по которым определяется сложность алгоритмов:
-
Если содержится цикл с n итерациями, то его сложность оценивается как O(n).
-
Если внутри одного цикла с n1 итерациями (внешний цикл) содержится цикл с n2 операциями (внутренний цикл), то сложность этих циклов оценивается как O(n1 * n2).
-
Если вызывается функция f(n), а затем g(n), то сложность составляет O(f(n) + g(n)).
-
Расчет сложности блока if: O(IF) = O(cond(n)) + max[O(b1(n)), O(b2(n))], где cond(n) - функция вычисления условия, O(b1(n)) - сложность вычисления блока при срабатывании условия, O(b2(n)) - сложность блока при не срабатывании условия.
Примеры алгоритмов с константной сложностью
-
Доступ к элементу массива по его индексу.
-
Стек на базе массива: операции pop, push, size, peek.
-
Доступ к элементу хэш-таблицы.
Примеры алгоритмов с линейной сложностью
-
Подсчет суммы значений элементов массива, т.к. содержится один цикл с n итерациями, на каждой итерации выполняется доступ к элементу массива за O(1) и суммирование переменной за O(1), поэтому f(n) = O(n) * O(1) * O(1) = O(n)
-
Поиск элемента в массиве (линейный поиск).
-
Обход двоичного дерева.
Примеры алгоритмов с квадратичной сложностью
-
Суммирование значений элементов двумерного массива (вложенный цикл).
-
Сортировка методом пузырька.
Примеры алгоритмов с логарифмической сложностью
Часто в эту категорию попадают алгоритмы, созданные по стратегии “разделяй и властвуй”, например, двоичный поиск: на каждой итерации пространство поиска сокращается вдвое, что означает, что итераций будет кратно меньше, чем n.
Бинарный поиск запускается только на отсортированных данных.
Примеры алгоритмов с линейно-логарифмической сложностью
Часто в эту категорию попадают алгоритмы, где данные разделяются на несколько более мелких частей, каждая из частей обрабатывается функцией с логарифмической сложностью, а затем все обработанные части данных собираются воедино с помощью линейной операции (в цикле).
-
Сортировка слиянием: выполняется n итераций, на каждой из которых выполняется операция mergeSort, сложность которой - O(logn), т.е. mergeSort выполнится n раз. Стоит отметить, что для этого алгоритма требуется дополнительная память на n элементов (сложность по памяти O(n)).
-
Быстрая сортировка.
Примеры алгоритмов с экспоненциальной сложностью
Расчет чисел Фибоначчи при помощи рекурсии - каждый вызов функции Фибоначчи приводит к двум новым рекурсивным вызовам.
Примеры алгоритмов с факториальной сложностью
Задача коммивояжёра (TSP). Полный перебор (brute force).
Структуры данных и их применение в алгоритмах
Массивы - упорядоченный набор n элементов одного типа, хранящихся в непрерывном блоке памяти.
+Быстрый доступ к элементам по индексу.
-Добавление/удаление элементов сопряжено с перевыделением памяти и копированием элементов в новый массив, что составляет сложность O(n), т.к. элементы копируются в цикле.
Списки - упорядоченный набор элементов одного типа, каждый элемент хранит ссылку на следующий элемент (элементы могут храниться в разных участках памяти).
+Быстрое добавление/удаление элементов.
-Доступ к элементам сопровождается обходом по списку, следовательно сложность операции составляет O(n) в худшем случае.
При добавлении элемента в середину списка, нужно в цикле пройти по элементам до опорного, а затем обновить ссылки элементов списка: опорный ссылается на добавляемый, добавляемый ссылается на следующий за опорным.
Хеш-таблицы хранят неупорядоченные пары ключ-значение. Для доступа к значению вычисляется хеш-функция от ключа. Получающееся хеш-значение играет роль индекса в массиве, по которому извлекается значение.
+Добавление, удаление, поиск элемента в среднем выполняются за O(1).
-При достижении определенного коэффициента заполнения необходимо осуществлять перестройку индекса хеш-таблицы: создать новый массив увеличенного размера и заново добавлять в него все пары, что составляет сложность O(N).
Словари или dictionaries хранят неупорядоченные пары ключ-значение, где тип ключей должен быть хешируемым, а значения ключей - уникальными.
+Быстрый доступ и удаление за O(1).
-Добавление элементов и поиск по значению может составлять O(n).
Стек - организован по принципу LIFO на основе массива или списка.
+Операции добавления элемента в стек (push), удаления элемента (pop), чтения (peek) выполняются за O(1).
Очередь - организована по принципу FIFO на основе массива или списка.
+Операции добавления элемента в очередь (enqueue), удаления элемента (dequeue), чтения из начала (front) и конца (rear) очереди выполняются за O(1).
-Если стек или очередь реализованы на базе массива, то добавление элементов может в худшем случае составлять O(n), что связано с перераспределением памяти.
Деревья - наиболее распространены двоичные деревья, используемые для хранения иерархических данных или же упорядоченных.
+Вставка, добавление и поиск в среднем за O(logn), в худшем - O(n).
Некоторые рекомендации для разработки на .NET
Список в .NET реализован как динамический массив, что обеспечивает быстрый доступ к его элементам по индексам: List<T> содержит свойства Count, характеризующее число элементов списка и размер массива Capacity. При количестве элементов, превышающем Capacity, массив пересоздается с увеличенным Capacity и с копированием элементов (O(n)). Capacity всегда берется с запасом, начиная с 4 и увеличивается в 2 раза (при достижении размера 2Гб будет ошибка переполнения). По такому же принципу реализован и StringBuilder, HashSet<T> и Dictionary<TKey,TValue>. Класс LinkedList<T> представляет собой двухсвязный список.
Свойство Count имеет вычислительную сложность O(1).
Типы Array и List предоставляют метод Sort, реализованный на основе гибридного алгоритма сортировки Introsort - интроспективная сортировка (предложен Дэвидом Мюссером в 1997г), в котором сочетаются Быстрая сортировка, сортировка кучей и вставками, что гарантирует сложность O(nlogn) для худшего случая.
Типы SortedSet<T> и SortedDictionary<TKey,TValue> построены на основе красно-черных деревьев, а тип SortedList<TKey,TValue> построен на основе двух массивов, в одном из которых хранятся ключи, а в другом - значения, отсортированные по ключу. Для хранения упорядоченных пар ключ-значение можно выбрать SortedList или SortedDictionary:
Операция |
SortedList |
SortedDictionary |
Доступ по ключу |
Чтение - O(logn), Запись по существующему ключу - O(logn) |
|
Доступ по целочисленному индексу |
Свойства Keys и Values с возвращаемым типом IList<T> |
Не поддерживается |
Добавление элемента |
O(logn) если порядок не нарушается, O(n) - если нужна переcортировка или перераспределение памяти |
O(logn) |
Удаление элемента |
O(n) |
O(logn) |
Расход памяти |
Меньше |
Больше |
При работе с non-generic коллекциями с элементами типа Object, требуется выполнять приведение типов (упаковка/boxing типов-значений в object), что чревато ошибками и снижением производительности. Предпочитайте им generic типы:
Non-generic тип |
Предпочтительный generic тип |
Если коллекция нужна только для перебора ее элементов в foreach (только для чтения), то используйте типы из System.Collections.IEnumerable. Т.к. эти типы также queryable types, то к ним можно применять фильтрацию, группировку, сортировку с LINQ.
Для хранения пар ключ-значение используйте:
-
Dictionary<TKey,TValue> если одному ключу соответствует одно значение
-
KeyedCollection<TKey,TItem> если ключ встроен в значение
-
NameValueCollection если для одного ключа может быть несколько значений
-
OrderedDictionary<TKey,TValue> нужен доступ к парам по индексу (метод GetAt)
-
SortedList<TKey,TValue> и SortedDictionary<TKey,TValue> пары отсортированы в порядке, определенном в реализации IComparer<T>.
Хранение неоднородных элементов: List<Object>, OrderedDictionary.
Хранение набора уникальных элементов: HashSet<T>, SortedSet<T>.
Быстрый поиск и извлечение данных:
-
ListDictionary для коллекций < 10 пар ключ-значение
-
Dictionary<TKey,TValue>, SortedDictionary<TKey,TValue> для больших коллекций.
Для хранения коллекции строк: StringCollection, StringDictionary.
При доступе к данным из нескольких потоков берите типы из System.Collections.Concurrent.
Везде, где только возможно, предпочитайте использовать иммутабельные типы данных, например из System.Collections.Immutable - эти типы также потокобезопасны.
Разница в производительности операций mutable/immutable типов:
Mutable |
Amortized |
Worst Case |
Complexity immutable |
Stack<T>.Push |
O(1) |
O(n) |
O(1) |
Queue<T>.Enqueue |
O(1) |
O(n) |
O(1) |
List<T>.Add |
O(1) |
O(n) |
O(log n) |
List<T>.Item[Int32] |
O(1) |
O(1) |
O(log n) |
List<T>.Enumerator |
O(n) |
O(n) |
O(n) |
HashSet<T>.Add, lookup |
O(1) |
O(n) |
O(log n) |
SortedSet<T>.Add |
O(log n) |
O(n) |
O(log n) |
Dictionary<T>.Add |
O(1) |
O(n) |
O(log n) |
Dictionary<T> lookup |
O(1) |
O(n) |
O(log n) |
SortedDictionary<T>.Add |
O(log n) |
O(n log n) |
O(log n) |
Тип ImmutableList<T> использует двоичное дерево для хранения элементов, что замедляет доступ по индексу.
А какие методы и структуры данных Вы предпочитаете использовать в решении задач? Какие трудности возникали при неправильном выборе структуры данных или алгоритма?
Автор: Alex9889