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

• описание логики работы алгоритма было понятным
• чтобы операции алгоритма можно было выполнить точно за то время, которым мы располагаем и
• используя тот объем памяти, которым мы располагаем.

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

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

Интеллектуальная эффективность. При анализе интеллектуальной сложности алгоритма исследуется понятность алгоритмов и сложность их разработки.

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

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

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

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

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

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

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

Алгоритм быстрой сортировки характеризуется также и большей интеллектуальной сложностью по сравнению с алгоритмом сортировки вставками. Если предложить сотне людей отсортировать последовательность объектов, то вероятнее всего, большинство из них используют алгоритм сортировки выборками. Маловероятно также, что кто-то из них воспользуется быстрой сортировкой. Причины большей интеллектуальной и пространственной сложности быстрой сортировки очевидны: алгоритм рекурсивный, его достаточно трудно описать, алгоритм длиннее (имеется в виду текст программы), чем более простые алгоритмы сортировки.

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