1. Нотация О большое для оценки сложности алгоритмов

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

3. Некоторые рекомендации для разработки на .NET

При написании алгоритмов нужно учитывать их масштабируемость. Для этих целей используется понятие «О большое», представленное Паулем Бахманном в 1894 году для того, чтобы приблизительно оценивать, как время выполнения алгоритма будет расти при увеличении размеров входных данных.

Пусть f(n) — время выполнения алгоритма, а g(n)  - временная сложность, которая проверяется для алгоритма. Тогда f(n)=O(g(n)), если существует константа k (k > 0) и n₀, такие, что f(n) <= kg(n) для всех n, начиная с некоторого n₀ (n > n₀).

Пример.

Пусть f(n)=4n²-8n+17

тогда f(n)=O(n²), поскольку

4n²-8n+17 <= 10n² при n>2

Говоря о сложности алгоритмов, часто рассматривается наихудшее время работы алгоритма, и для его описания используются следующие О нотации: 

O(1) - константная сложность - время выполнения такого алгоритма не зависит от длины исходных данных 

O(n) - линейная сложность - время выполнения такого алгоритма, прямо пропорционально длине обрабатываемых исходных данных, т.е. при увеличении размера n в 10 раз, время работы алгоритма возрастет также в 10 раз 

O(n²) - квадратичная сложность - время пропорциональное квадрату длины входных данных, т.е. при увеличении размера n в 10 раз, время работы алгоритма возрастет в 10²=100 раз.

O(logn) - логарифмическая сложность - время будет расти меньше, в сравнении с линейной сложностью, но быстрее, чем у константной, например, при увеличении размера n в 10 раз, время работы алгоритма возрастет в log₂10 = 3.32 раза.  

O(nlogn) - линейно-логарифмическая сложность - время будет расти быстрее, чем у O(n), но медленнее, чем у O(n²). К примеру, при увеличении размера n в 10 раз, время работы алгоритма возрастет в 10log₂10 = 10*3.32 = 33.2 раза.

Критерии, по которым определяется сложность алгоритмов:

• Если содержится цикл с n итерациями, то его сложность оценивается как O(n).

• Если внутри одного цикла с n₁ итерациями (внешний цикл) содержится цикл с n₂ операциями (внутренний цикл), то сложность этих циклов оценивается как O(n₁ * n₂).

• Если вызывается функция f(n), а затем g(n), то сложность составляет O(f(n) + g(n)).

• Расчет сложности блока if: O(IF) = O(cond(n)) + max[O(b₁(n)), O(b₂(n))], где cond(n) - функция вычисления условия, O(b₁(n)) - сложность вычисления блока при срабатывании условия, O(b₂(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:

При работе с non-generic коллекциями с элементами типа Object, требуется выполнять приведение типов (упаковка/boxing типов-значений в object), что чревато ошибками и снижением производительности. Предпочитайте им 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 типов:

Тип ImmutableList<T> использует двоичное дерево для хранения элементов, что замедляет доступ по индексу.

А какие методы и структуры данных Вы предпочитаете использовать в решении задач? Какие трудности возникали при неправильном выборе структуры данных или алгоритма?