Что нужно знать при написании алгоритмов на .NET

в 20:17, , рубрики: Коллекции .NET, сложность алгоритмов, структуры данных
  1. Нотация О большое для оценки сложности алгоритмов

  2. Структуры данных и их применение в алгоритмах

  3. Некоторые рекомендации для разработки на .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)

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(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<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 типы:

Если коллекция нужна только для перебора ее элементов в foreach (только для чтения), то используйте типы из System.Collections.IEnumerable. Т.к. эти типы также queryable types, то к ним можно применять фильтрацию, группировку, сортировку с LINQ.

Для хранения пар ключ-значение используйте: 

Хранение неоднородных элементов: List<Object>, OrderedDictionary.

Хранение набора уникальных элементов: HashSet<T>, SortedSet<T>.

Быстрый поиск и извлечение данных:

Для хранения коллекции строк: StringCollectionStringDictionary.

При доступе к данным из нескольких потоков берите типы из 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js