1.2. Зачем изучать алгоритмы? Эффективность алгоритмов

Во-первых, алгоритмы являются жизненно необходимыми составляющими для решения любых задач по различным направлениям компьютерных наук. Алгоритмы играют ключевую роль на современном этапе развития технологий. Здесь можно вспомнить такие распространенные задачи, как:

• решения математических уравнений различной сложности, нахождения произведения матриц, обратных матриц;
• нахождения оптимальных путей транспортировки товаров и людей;
• нахождения оптимальных вариантов распределения ресурсов между различными узлами (производителями, станками, работниками, процессорами и т.д.);
• нахождения в геноме последовательностей, которые совпадают;
• поиск информации в глобальной сети Интернет;
• принятия финансовых решений в электронной коммерции;
• обработка и анализ аудио и видео информации.

Этот список можно продолжать и продолжать и, собственно говоря, почти невозможно найти такую ​​область компьютерных наук и информатики, где бы ни использовались те или иные алгоритмы.

Во-вторых, качественные и эффективные алгоритмы могут быть катализаторами прорывов в отраслях, которые являются на первый взгляд далеки от компьютерных наук (квантовая механика, экономика и финансы, теория эволюции).

И, в-третьих, изучение алгоритмов это также невероятно интересный процесс, который развивает наши математические способности и логическое мышление.

1.3. Эффективность алгоритмов

Предположим, быстродействие компьютера и объем его памяти можно увеличивать до бесконечности. Была бы тогда необходимость в изучении алгоритмов? Да, но только для того, чтобы продемонстрировать, что метод развязку имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы произвольный корректный метод решения задачи. Конечно, тогда чаще всего избирался бы метод, который легче реализовать.

Сегодня очень мощные компьютеры, но их быстродействие не является бесконечно большой, как и память. Таким образом, при исчислении - это такой же ограниченный ресурс, как и объем требуемой памяти. Этими ресурсами следует пользоваться разумно, чем и способствует применение алгоритмов, которые эффективны в плане использования ресурсов времени и памяти.

Алгоритмы, разработанные для решения одной и той же задачи, часто могут очень сильно отличаться по эффективности. Эти различия могут быть намного больше заметными, чем те, которые вызваны применением различного аппаратного и программного обеспечения.

Как отмечалось выше, в этом разделе центральную роль будет посвящено задачи сортировка. Первый алгоритм, который будет рассматриваться - сортировка включением, для своей работы требует времени, количество которого оценивается как c₁n², где n - размер входных данных (Количество элементов в последовательности для сортировки), c₁ - Некоторая постоянная. Это выражение указывает на то, как зависит время работы алгоритма от объема исходных данных. В случае сортировки включением эта зависимость является квадратичной. Второй алгоритм - сортировка слиянием - требует времени, количество которого оценивается как ₂nLog₂n. Обычно константа сортировки включением меньше константы сортировки слиянием, то есть c12 растет быстрее с увеличением n, чем функция яLog₂n. И для некоторого значения n = n₀ будет достигнуто такой момент, когда влияние разницы констант перестанет иметь значение и в дальнейшем функция c₂nLog₂n будет меньше c₁n² для любых n > n₀.

Для демонстрации этого рассмотрим два компьютера - А и Б. Компьютер А более быстрый и на нем работает алгоритм сортировки, а компьютер Б более медленный и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоит из миллиона чисел. Предположим, что компьютер А выполняет миллиард операций в секунду, а компьютер Б - лишь десять миллионов, есть А работает в 100 раз быстрее Б. Чтобы разница стала более ощутимой, допустим что код метода включения написан лучшим программистом в мире с использованием команд процессору, и для сортировки n чисел с этим алгоритмом нужно выполнить 2n² операций (то есть C₁= 2). Сортировка методом слияния на компьютере Б написано программистом начинающим с использованием языка высокого уровня и полученный код требует 50nlog₂n операций (то есть c₂= 50). Таким образом, для сортировки миллиона чисел компьютеру А потребуется

а компьютеру Б -

Поэтому, использование кода, время работы которого растет медленнее, даже при плохом компьютере и плохом компиляторе требует на порядок меньше процессорного времени! Для сортировка 10000000 цифр преимущество сортировки слиянием становится еще более ощутимой: если сортировка включением требует для такой задачи примерно 2,3 дня, то для сортировка слиянием - меньше 20 минут. Общее правило таково: чем больше количество элементов для сортировки, тем заметнее преимущество сортировки слиянием. Приведенный выше пример демонстрирует, что алгоритмы, как и программное обеспечение компьютеру, представляют собой технологию. Общая производительность системы настолько же зависит от эффективности алгоритма, как и от мощности аппаратных средств.