[00:02] ключ к пониманию эффективности алгоритмов. Big O измеряет, как время выполнения масштабируется в зависимости от размера входных данных, что имеет решающее значение для оптимизации производительности Cod. Давайте разберем распространенные обозначения от самого быстрого к самому медленному. Время выполнения за постоянное время
[00:18] остается неизменным независимо от размера входных данных. Индексы массивов, операции с осью или хеш-таблицей — хорошие примеры. Время выполнения за логарифмическое время примеры. Время выполнения за логарифмическое время медленно увеличивается по мере роста входных данных; бинарный
[00:32] поиск — классический пример. Эффективен для больших наборов данных; удвоение размера входных данных — всего лишь еще одна операция. Время выполнения за линейное время растет прямо пропорционально входным данным, например, поиск максимума в несортированном массиве. Если вам необходимо
[00:48] обработать каждый элемент, то здесь начинается линейное арифметическое время. Именно здесь работают эффективные алгоритмы сортировки: сортировка слиянием, быстрая сортировка, пирамидальная сортировка — наилучший из
[01:00] возможных вариантов для сортировки на основе сравнений. Время выполнения за квадратичное время растет пропорционально квадрату размера входных данных. Базовые алгоритмы сортировки, такие как пузырьковая сортировка, — обратите внимание на вложенные циклы, итерирующие по одним и тем же
[01:14] данным. Время выполнения за кубическое время растет пропорционально кубу размера входных данных. Наивное умножение матриц — хороший пример. Три вложенных цикла часто указывают на кубическое время.
[01:26] экспоненциальное время, удваивающееся с каждым дополнительным входным элементом. Вы увидите это в некоторых рекурсивных алгоритмах. Обработка небольших входных данных может занять много времени. Факториальное время, удваивающееся с размером входных данных, чрезвычайно быстро растет. Генерация всех
[01:42] перестановок помещается здесь. Непрактично для нетривиальных размеров входных данных. Теперь вот нетривиальных размеров входных данных. Теперь вот важная часть: BigO — это только начало. Производительность в реальных условиях может отличаться из-за таких факторов, как кэширование, использование памяти и
[01:56] особенности оборудования. В современных процессорах максимизация попаданий в кэш иногда может быть более эффективной, чем снижение сложности алгоритма. Два примера: первый —
[02:08] сложности алгоритма. Два примера: первый — обход массива. Рассмотрим двумерный массив. Обход по строкам часто быстрее, чем по столбцам, хотя оба варианта имеют квадратичную временную сложность. Построчная ось максимизирует последовательный доступ к памяти и
[02:22] последовательный доступ к памяти и дружественна к кэшу. Далее — связанный список против массива. Оба имеют линейную временную сложность для обхода, но массивы часто превосходят связанные списки из-за локальности кэша. Элементы массива расположены последовательно в памяти, в то время как элементы
[02:35] связанного списка могут быть разбросаны. Итак, какой ваш вывод? Используйте PiO в качестве Профилируйте свой код, понимайте свое оборудование и оптимизируйте его для реальных условий, если хотите.
[02:50] Возможно, вас также заинтересует новостная рассылка по системному проектированию, которая охватывает темы и тенденции в проектировании крупномасштабных систем. Ей доверяют 1 миллион читателей. Подпишитесь на этот million readers subscribe that blog blog. byby go.com