Как строить эффективные алгоритмы?

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

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

Шаги для построения эффективного алгоритма:

1. Более строгая формулировка решаемой задачи, отделение существенного от неважного.
2. Либо самостоятельно улучшить алгоритм, пришедший на ум первым, либо воспользоваться уже известными эффективными алгоритмами.
3. Чтобы лучше понять алгоритм нужно выполнить его вручную (трассировка алгоритмов).
4. Прежде чем анализировать эффективность алгоритма, нужно доказать, что данный алгоритм правильно решает задачу. Тут следует подчеркнуть важность проверок промежуточных состояний (assertions) и инвариантов цикла для доказательства корректности алгоритма.
5. Превратить алгоритмы в программы и протестировать их, а затем сравнить результаты работы реальных программ с полученными посредством теоретического анализа.

При создании программных продуктов нужно обращать внимание на:

• временную эффективность программ;
• разумное использование памяти.

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

Ограничения могут быть связаны:

• с производительностью компьютеров;
• со сложностью решаемой задачи.

В начале 80-х годов зачастую общий размер программы и данных не превышал 64 К.

До сих пор существует активное сообщество, использующее платформу DOS и разрабатывающее для неё ПО.

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