Я предполагаю, что вы программист. Возможно, вы новичок в области компьютерных наук или опытный инженер-программист. Независимо от того, где вы находитесь в этом спектре, алгоритмы и структуры данных имеют значение. Не только как теоретические концепции, но и как строительные блоки, используемые для решения бизнес-задач.
Конечно, вы знаете, как использовать класс C # List или Stack , но понимаете ли вы, что происходит под покровом? Если нет, то действительно ли вы принимаете лучшие решения о том, какие алгоритмы и структуры данных вы используете?
Осмысленное понимание алгоритмов и структур данных начинается с того, что у них есть способ выразить и сравнить их относительную стоимость.
Асимптотический анализ
Когда мы говорим об измерении стоимости или сложности алгоритма, мы на самом деле говорим об анализе алгоритма, когда входные наборы очень велики. Анализ того, что происходит, когда число входов становится очень большим, называется асимптотическим анализом. Как изменяется сложность алгоритма применительно к десяти, или тысяче, или десяти миллионам предметов? Если алгоритм выполняется за пять миллисекунд с тысячей элементов, что мы можем сказать о том, что произойдет, если он будет работать с одним миллионом? Это займет пять секунд или пять лет? Не лучше ли разобраться с этим перед вашим клиентом?
Этот материал имеет значение!
Уровень роста
Скорость роста описывает, как изменяется сложность алгоритма при увеличении размера ввода. Это обычно представляется с использованием нотации Big-O. В нотации Big-O используется заглавная буква O («порядок») и формула, выражающая сложность алгоритма. Формула может иметь переменную n, которая представляет размер ввода. Ниже приведены некоторые общие функции порядка, которые мы увидим в этой книге, но этот список ни в коем случае не является полным.
Константа — O (1)
Алгоритм O (1) — это алгоритм, сложность которого постоянна независимо от размера входного размера. «1» не означает, что существует только одна операция или что операция занимает небольшое количество времени. Это может занять одну микросекунду или один час. Дело в том, что размер ввода не влияет на время, которое занимает операция.
|
1
2
3
4
|
public int GetCount(int[] items)
{
return items.Length;
}
|
Линейный — O (n)
Алгоритм O (n) — это алгоритм, сложность которого растет линейно с размером входных данных. Разумно ожидать, что если размер ввода равен пяти миллисекундам, то ввод с тысячей элементов займет пять секунд.
Вы часто можете распознать алгоритм O (n), ища механизм зацикливания, который обращается к каждому члену.
|
01
02
03
04
05
06
07
08
09
10
|
public long GetSum(int[] items)
{
long sum = 0;
foreach (int i in items)
{
sum += i;
}
return sum;
}
|
Логарифмический — O (log n)
Алгоритм O (log n) — это алгоритм, сложность которого логарифмична его размеру. Многие алгоритмы разделяй и властвуй попадают в эту корзину. Двоичное дерево поиска Contains метод, реализующий алгоритм O (log n).
Линеарифмический — O (n log n)
Линейный алгоритм, или логлинейный, — это алгоритм, имеющий сложность O (n log n). Некоторые алгоритмы «разделяй и властвуй» попадают в эту корзину. Мы увидим два примера, когда мы рассмотрим сортировку слиянием и быструю сортировку.
Квадратичный — O (n ^ 2)
Алгоритм O (n ^ 2) — это алгоритм, сложность которого квадратична своему размеру. Хотя это не всегда можно избежать, использование квадратичного алгоритма является потенциальным признаком того, что вам необходимо пересмотреть свой алгоритм или выбор структуры данных. Квадратичные алгоритмы плохо масштабируются по мере увеличения размера входных данных. Например, для массива с 1000 целыми числами потребуется 1 000 000 операций. Для ввода с одним миллионом элементов потребуется триллион (1 000 000 000 000) операций. Чтобы представить это в перспективе, если для завершения каждой операции требуется одна миллисекунда, алгоритму O (n ^ 2), который получает входные данные из одного миллиона элементов, потребуется около 32 лет. Создание этого алгоритма в 100 раз быстрее все равно займет 84 дня.
Мы увидим пример квадратичного алгоритма, когда мы рассмотрим пузырьковую сортировку.
Лучший, средний и худший случай
Когда мы говорим, что алгоритм — это O (n), что мы на самом деле говорим? Мы говорим, что алгоритм в среднем равен O (n)? Или мы описываем лучший или худший сценарий?
Обычно мы имеем в виду сценарий наихудшего случая, если общий случай и худший случай не сильно отличаются. Например, мы увидим примеры в этой книге, где алгоритм в среднем равен O (1), но периодически становится O (n) (см. ArrayList.Add ). В этих случаях я опишу алгоритм в среднем как O (1), а затем объясню, когда сложность изменится.
Ключевым моментом является то, что выражение O (n) не означает, что это всегда n операций. Может быть меньше, но не должно быть больше.
Что мы измеряем?
Когда мы измеряем алгоритмы и структуры данных, мы обычно говорим об одном из двух: количество времени, которое требуется для выполнения операции (сложность работы), или количество ресурсов (память), которые использует алгоритм (сложность ресурса).
Алгоритм, который работает в десять раз быстрее, но использует в десять раз больше памяти, может быть вполне приемлемым в серверной среде с огромным объемом доступной памяти, но может не подходить во встроенной среде, где доступная память строго ограничена.
В этой книге я сосредоточусь прежде всего на сложности операций, но в разделе Алгоритмы сортировки мы увидим несколько примеров сложности ресурсов.
Вот некоторые конкретные примеры того, что мы могли бы измерить:
- Операции сравнения (больше, меньше, равно).
- Назначения и обмен данными.
- Распределение памяти.
Контекст выполняемой операции обычно говорит вам, какой тип измерения выполняется.
Например, при обсуждении сложности алгоритма, который ищет элемент в структуре данных, мы почти наверняка говорим об операциях сравнения. Поиск обычно является операцией только для чтения, поэтому не должно быть необходимости выполнять назначения или выделять память.
Однако, когда мы говорим о сортировке данных, было бы логично предположить, что мы можем говорить о сравнениях, назначениях или распределениях. В случаях, когда может быть неоднозначность, я укажу, к какому типу измерения относится сложность.
Следующий
Это завершает первую часть об алгоритмах и структурах данных. Далее мы перейдем к связанному списку.