Что нужно знать при написании алгоритмов на .NET
Нотация О большое для оценки сложности алгоритмов
Структуры данных и их применение в алгоритмах
Некоторые рекомендации для разработки на .NET
При написании алгоритмов нужно учитывать их масштабируемость. Для этих целей используется понятие «О большое», представленное Паулем Бахманном в 1894 году для того, чтобы приблизительно оценивать, как время выполнения алгоритма будет расти при увеличении размеров входных данных.
Пусть f (n) — время выполнения алгоритма, а g (n) — временная сложность, которая проверяется для алгоритма. Тогда f (n)=O (g (n)), если существует константа k (k > 0) и n0, такие, что f (n) <= kg(n) для всех n, начиная с некоторого n0 (n > n0).
4n2–8n+17=O (n2)
Пример.
Пусть 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 (1), O (logn), самое худшее y O (n!)
Критерии, по которым определяется сложность алгоритмов:
Если содержится цикл с 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
Свойство Count имеет вычислительную сложность O (1).
Типы Array и List предоставляют метод Sort, реализованный на основе гибридного алгоритма сортировки Introsort — интроспективная сортировка (предложен Дэвидом Мюссером в 1997 г), в котором сочетаются Быстрая сортировка, сортировка кучей и вставками, что гарантирует сложность O (nlogn) для худшего случая.
Типы SortedSet
Операция | SortedList | SortedDictionary |
Доступ по ключу | Чтение — O (logn), Запись по существующему ключу — O (logn) | |
Доступ по целочисленному индексу | Свойства Keys и Values с возвращаемым типом IList | Не поддерживается |
Добавление элемента | O (logn) если порядок не нарушается, O (n) — если нужна переcортировка или перераспределение памяти | O (logn) |
Удаление элемента | O (n) | O (logn) |
Расход памяти | Меньше | Больше |
При работе с non-generic коллекциями с элементами типа Object, требуется выполнять приведение типов (упаковка/boxing типов-значений в object), что чревато ошибками и снижением производительности. Предпочитайте им generic типы:
Если коллекция нужна только для перебора ее элементов в foreach (только для чтения), то используйте типы из System.Collections.IEnumerable. Т.к. эти типы также queryable types, то к ним можно применять фильтрацию, группировку, сортировку с LINQ.
Для хранения пар ключ-значение используйте:
Хранение неоднородных элементов: List, OrderedDictionary.
Хранение набора уникальных элементов: HashSet
Быстрый поиск и извлечение данных:
Для хранения коллекции строк: StringCollection, StringDictionary.
При доступе к данным из нескольких потоков берите типы из System.Collections.Concurrent.
Везде, где только возможно, предпочитайте использовать иммутабельные типы данных, например из System.Collections.Immutable — эти типы также потокобезопасны.
Разница в производительности операций mutable/immutable типов:
Mutable | Amortized | Worst Case | Complexity immutable |
Stack | O (1) | O (n) | O (1) |
Queue | O (1) | O (n) | O (1) |
List | O (1) | O (n) | O (log n) |
List | O (1) | O (1) | O (log n) |
List | O (n) | O (n) | O (n) |
HashSet | O (1) | O (n) | O (log n) |
SortedSet | O (log n) | O (n) | O (log n) |
Dictionary | O (1) | O (n) | O (log n) |
Dictionary | O (1) | O (n) | O (log n) |
SortedDictionary | O (log n) | O (n log n) | O (log n) |
Тип ImmutableList
А какие методы и структуры данных Вы предпочитаете использовать в решении задач? Какие трудности возникали при неправильном выборе структуры данных или алгоритма?
