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

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

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

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

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

Однако в этом определении отсутствуют некоторые ключевые подробно- сти, хотя нашей главной целью и является быстрое решение реальных задач на реальных компьютерах. Во-первых, в нем не указано, где и насколько хорошо реализуется алгоритм. Даже плохой алгоритм может быстро отработать с ма- лым размером тестовых данных на исключительно быстром процессоре; даже хорошие алгоритмы могут быстро выполняться при небрежном программирова- нии. Кроме того, какие входные данные можно считать «реальными»? Полный диапазон входных данных, которые могут встречаться на практике, неизвестен, а некоторые наборы данных могут создавать значительно больше сложностей при обработке. Наконец, предлагаемое определение не учитывает, насколько хорошо (или плохо) алгоритм масштабируется с ростом задачи до непредвиден- ных уровней.

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

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Попытка портрета
  2. Попытка заглушить чувства алкоголем
  3. Глава 10. Как противостоять попыткам манипуляции.
  4. Отстраненность - попытка говорить отвлеченно.
  5. Обращение к наркотикам —попытка не ощущать то, что мы чувствуем.
  6. Часть первая. Первые шаги на пути к успеху
  7. Первые патриотические издания.
  8. Первые признаки дисбаланса энергии
  9. Итак, подведем первые итоги.
  10. Журналистика и социология: первые опыты взаимодействия
  11. Журналистика и социология: первые опыты взаимодействия
  12. Первые признаки дисбаланса энергии в канале:
  13. Первые признаки дисбаланса энергии в канале
  14. Выводы. Первые шаги на пути к успеху
  15. Вторая стадия: делающий свои первые шаги малыш
  16. Самоуничижение на уровне зрелости малыша, делающего свои первые шаги
  17. ЭФФЕКТИВНОСТЬ
  18. Эффективность социальной работы