Первые попытки определения эффективности
Первый серьезный вопрос, на который нужно ответить, выглядит так: как преобразовать размытое понятие «эффективный алгоритма» в нечто более конкретное?
На первый взгляд рабочее определение эффективности могло бы выглядеть так.
Предлагаемое определение эффективности (1): алгоритм называется эффективным, если его реализация быстро выполняется на реальных входных данных.
Однако в этом определении отсутствуют некоторые ключевые подробности, хотя нашей главной целью и является быстрое решение реальных задач на реальных компьютерах. Во-первых, в нем не указано, где и насколько хорошо реализуется алгоритм.
Даже плохой алгоритм может быстро отработать с малым размером тестовых данных на исключительно быстром процессоре; даже хорошие алгоритмы могут быстро выполняться при небрежном программировании.
Кроме того, какие входные данные можно считать «реальными»? Полный диапазон входных данных, которые могут встречаться на практике, неизвестен, а некоторые наборы данных могут создавать значительно больше сложностей при обработке.
Наконец, предлагаемое определение не учитывает, насколько хорошо (или плохо) алгоритм масштабируется с ростом задачи до непредвиденных уровней.
Типичная ситуация: два совершенно разных алгоритма примерно одинаково работают на входных данных размера 100; при 10-кратном увеличении размера данных один алгоритм продолжает работать быстро, а выполнение другого резко замедляется.
Итак, нам хотелось бы иметь конкретное определение эффективности — не зависящее от платформы и набора входных данных и имеющее прогностическое значение в отношении увеличения размера входных данных.
Прежде чем переходить к рассмотрению практических выводов из этого утверждения, мы можем по крайней мере проанализировать неявное высокоуровневое предположение, из которого оно вытекает: что ситуацию следует рассматривать с более математической точки зрения.
В качестве ориентира возьмем задачу устойчивых паросочетаний. У входных данных имеется естественный параметр — «размер» N; за него можно принять общий размер представления всех списков предпочтений, поскольку именно они будут передаваться на вход любого алгоритма для решения задачи. Значение N тесно связано с другим естественным параметром этой задачи: n, количеством мужчин и количеством женщин.
Всего существуют 2n списков предпочтений, каждый из которых имеет длину n, поэтому мы можем считать, что N = 2n2, игнорируя второстепенные подробности реализации представления данных.
При рассмотрении задачи мы будем стремиться к описанию алгоритмов на высоком уровне, а затем проводить математический анализ времени выполнения как функции размера входных данных N.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу