Первые попытки определения эффективности

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

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

Предлагаемое определение эффективности (1): алгоритм называется эффективным, если его реализация быстро выполняется на реальных входных данных.

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

Даже плохой алгоритм может быстро отработать с малым размером тестовых данных на исключительно быстром процессоре; даже хорошие алгоритмы могут быстро выполняться при небрежном программировании.

Кроме того, какие входные данные можно считать «реальными»? Полный диапазон входных данных, которые могут встречаться на практике, неизвестен, а некоторые наборы данных могут создавать значительно больше сложностей при обработке.

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

Типичная ситуация: два совершенно разных алгоритма примерно одинаково работают на входных данных размера 100; при 10-кратном увеличении размера данных один алгоритм продолжает работать быстро, а выполнение другого резко замедляется.

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

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

В качестве ориентира возьмем задачу устойчивых паросочетаний. У входных данных имеется естественный параметр — «размер» N; за него можно принять общий размер представления всех списков предпочтений, поскольку именно они будут передаваться на вход любого алгоритма для решения задачи. Значение N тесно связано с другим естественным параметром этой задачи: n, количеством мужчин и количеством женщин.

Всего существуют 2n списков предпочтений, каждый из которых имеет длину n, поэтому мы можем считать, что N = 2n2, игнорируя второстепенные подробности реализации представления данных.

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