0 added
0 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>Когда мы говорим об алгоритмах, нельзя не упомянуть их<strong>сложность</strong>. Она обозначается как<em>Big O</em>и указывает, насколько эффективен тот или иной алгоритм.</p>
1
<p>Когда мы говорим об алгоритмах, нельзя не упомянуть их<strong>сложность</strong>. Она обозначается как<em>Big O</em>и указывает, насколько эффективен тот или иной алгоритм.</p>
2
<p>Как вы помните, есть<a>много алгоритмов сортировок</a>. Они выполняют одну и ту же задачу, но при этом у них разная<strong>сложность</strong>- то есть количество выполняемых операций алгоритмом для достижения своей цели. Разные способы сортировки требуют очень разного количества проходов по массиву. Конкретное количество операций зависит от входных данных - например, для уже отсортированного массива количество операций будет минимальным (но они все равно будут, потому что алгоритм должен убедиться в том, что массив отсортирован).</p>
2
<p>Как вы помните, есть<a>много алгоритмов сортировок</a>. Они выполняют одну и ту же задачу, но при этом у них разная<strong>сложность</strong>- то есть количество выполняемых операций алгоритмом для достижения своей цели. Разные способы сортировки требуют очень разного количества проходов по массиву. Конкретное количество операций зависит от входных данных - например, для уже отсортированного массива количество операций будет минимальным (но они все равно будут, потому что алгоритм должен убедиться в том, что массив отсортирован).</p>
3
<p><em>Big O</em>показывает, насколько увеличится количество операций при увеличении объема данных. Рассмотрим пару примеров:</p>
3
<p><em>Big O</em>показывает, насколько увеличится количество операций при увеличении объема данных. Рассмотрим пару примеров:</p>
4
<ul><li>Доступ к элементу массива по индексу. Сложность этой операции не зависит от размеров массива. Это постоянная сложность<strong>O(1)</strong></li>
4
<ul><li>Доступ к элементу массива по индексу. Сложность этой операции не зависит от размеров массива. Это постоянная сложность<strong>O(1)</strong></li>
5
<li>Печати на экран всех элементов массива с помощью обычного перебора. В худшем случае количество выполняемых операций будет равно $n$ - количеству элементов. Это линейная сложность<strong>O(n)</strong></li>
5
<li>Печати на экран всех элементов массива с помощью обычного перебора. В худшем случае количество выполняемых операций будет равно $n$ - количеству элементов. Это линейная сложность<strong>O(n)</strong></li>
6
</ul><p>Что такое "худший случай"? Количество операций будет разным даже при работе с массивами одного размера - все зависит от состояния начального массива.</p>
6
</ul><p>Что такое "худший случай"? Количество операций будет разным даже при работе с массивами одного размера - все зависит от состояния начального массива.</p>
7
<p>Проведем аналогию с кубиком Рубика. Чтобы его собрать, нужно провести какое-то количество действий. Их число зависит от положения, в котором находятся его грани перед сборкой. В некоторых случаях действий понадобится мало, в других - много. Худшим случаем называется ситуация, при которой нам понадобится максимальное количество действий.</p>
7
<p>Проведем аналогию с кубиком Рубика. Чтобы его собрать, нужно провести какое-то количество действий. Их число зависит от положения, в котором находятся его грани перед сборкой. В некоторых случаях действий понадобится мало, в других - много. Худшим случаем называется ситуация, при которой нам понадобится максимальное количество действий.</p>
8
<p>Алгоритмическая сложность всегда оценивается по худшему случаю для выбранного алгоритма.</p>
8
<p>Алгоритмическая сложность всегда оценивается по худшему случаю для выбранного алгоритма.</p>
9
<p>Для еще одного примера вспомним вложенные циклы и поиск пересечений в неотсортированных массивах.</p>
9
<p>Для еще одного примера вспомним вложенные циклы и поиск пересечений в неотсортированных массивах.</p>
10
<p>Для каждого элемента из одного массива мы проверяем каждый элемент другого массива. При этом мы используем либо цикл, либо функцию in_array() со сложностью O(n) - в худшем случае мы просмотрим весь массив.</p>
10
<p>Для каждого элемента из одного массива мы проверяем каждый элемент другого массива. При этом мы используем либо цикл, либо функцию in_array() со сложностью O(n) - в худшем случае мы просмотрим весь массив.</p>
11
<p>Если размеры обоих массивов одинаковы и равны n то поиск пересечений имеет квадратичную сложность<strong>O(n^2</strong>).</p>
11
<p>Если размеры обоих массивов одинаковы и равны n то поиск пересечений имеет квадратичную сложность<strong>O(n^2</strong>).</p>
12
<p>Одни алгоритмы эффективные, другие - не очень. Скорость работы неэффективных алгоритмов заметно падает даже при небольшом количестве элементов. Эффективные алгоритмы работают быстрее, и при этом они нередко потребляют больше памяти или запускаются параллельно. Часто в программировании эффективность - это компромисс. Выигрывая в одном месте, мы проиграем где-то в другом.</p>
12
<p>Одни алгоритмы эффективные, другие - не очень. Скорость работы неэффективных алгоритмов заметно падает даже при небольшом количестве элементов. Эффективные алгоритмы работают быстрее, и при этом они нередко потребляют больше памяти или запускаются параллельно. Часто в программировании эффективность - это компромисс. Выигрывая в одном месте, мы проиграем где-то в другом.</p>
13
<p>Во многом,<em>Big O</em>- это теоретическая оценка, на практике все может быть по-другому. Реальное время выполнения зависит от множества факторов, в том числе архитектуры процессора, операционной системы, языка программирования и типа доступа к памяти.</p>
13
<p>Во многом,<em>Big O</em>- это теоретическая оценка, на практике все может быть по-другому. Реальное время выполнения зависит от множества факторов, в том числе архитектуры процессора, операционной системы, языка программирования и типа доступа к памяти.</p>
14
<p>Вопрос эффективности кода довольно опасен. Например, в университетах программирование обычно изучают, начиная с алгоритмов. Из-за этого студентам может казаться, что эффективность - это главное, ведь код должен работать быстро. Такой подход приносит больше вреда, чем пользы. Дело в том, что эффективный код всегда сложнее неэффективного. Этот сложный код больше подвержен ошибкам, его труднее писать и модифицировать.</p>
14
<p>Вопрос эффективности кода довольно опасен. Например, в университетах программирование обычно изучают, начиная с алгоритмов. Из-за этого студентам может казаться, что эффективность - это главное, ведь код должен работать быстро. Такой подход приносит больше вреда, чем пользы. Дело в том, что эффективный код всегда сложнее неэффективного. Этот сложный код больше подвержен ошибкам, его труднее писать и модифицировать.</p>
15
<p>На практике настоящая эффективность нужна только в редких случаях. Обычно тормозит не код, а запросы к базе данных, сеть или что-то другое. Если конкретный участок кода выполняется медленно, это не всегда критично. Вполне возможно, что этот код работает с небольшим объемом памяти, вызывается все один раз и ни на что не влияет. К реальному замедлению может приводить совершенно другой фрагмент кода, который вызывается тысячи раз.</p>
15
<p>На практике настоящая эффективность нужна только в редких случаях. Обычно тормозит не код, а запросы к базе данных, сеть или что-то другое. Если конкретный участок кода выполняется медленно, это не всегда критично. Вполне возможно, что этот код работает с небольшим объемом памяти, вызывается все один раз и ни на что не влияет. К реальному замедлению может приводить совершенно другой фрагмент кода, который вызывается тысячи раз.</p>
16
<blockquote><p><em>Программисты тратят очень много времени, беспокоясь о некритичных местах кода и пытаясь оптимизировать их. Это всегда негативно сказывается на последующей отладке и поддержке. Поспешная оптимизация - это корень всех зол. В 97% случаев код лучше вообще не оптимизировать - так мы сэкономим время и сможем сосредоточиться на важных 3%. - Дональд Кнут</em></p>
16
<blockquote><p><em>Программисты тратят очень много времени, беспокоясь о некритичных местах кода и пытаясь оптимизировать их. Это всегда негативно сказывается на последующей отладке и поддержке. Поспешная оптимизация - это корень всех зол. В 97% случаев код лучше вообще не оптимизировать - так мы сэкономим время и сможем сосредоточиться на важных 3%. - Дональд Кнут</em></p>
17
</blockquote><p>Перед тем, как пытаться что-то оптимизировать, обязательно прочитайте<a>небольшую онлайн-книгу</a>, которая хорошо объясняет суть всех оптимизаций.</p>
17
</blockquote><p>Перед тем, как пытаться что-то оптимизировать, обязательно прочитайте<a>небольшую онлайн-книгу</a>, которая хорошо объясняет суть всех оптимизаций.</p>