Вывод уравнения работы

Шаг 1. Допустим, что любая реализация какого-либо алгоритма заключается в N – кратном выборе из словаря, состоящего из элементов.

Шаг 2. Предположим далее, что каждый выбор из словаря неслучаен. Исследования методов сортировки показали, что самым быстрым способом поиска в упорядоченном списке является двоичный поиск. С помощью него список многократно делится пополам до тех пор, пока не будет найден нужный элемент. Полученное в результате число сравним равно двоичному логарифму числа элементов в списке. Следовательно, эффективный процесс, эквивалентный двоичному поиску, требует log сравнений для нахождения элемента.

Шаг 3. На основании шагов №1 и №2 можно заключить, что программа порождается выполнением N ∙ log мысленных сравнений.

Шаг 4. Т. к. объём программы V определяется как

V = N∙ log , (1)

то из шага №3 следует, что он равен числу мысленных сравнений, затрачиваемых на порождение программы.

Шаг 5. Каждое мысленное сравнение содержит ряд элементарных мыслительных различений. Их число является мерой сложности задачи. Из предыдущих результатов, полученных Холстедом, получается, что уровень программы L является величиной, обратной её сложности.

Шаг 6. Объём V равен числу мыслительных сравнений. Величина, обратная уровню программы, т. е. 1/ L, есть среднее число элементарных численных различений, входящих в каждое мысленное сравнение. Потому общее число элементарных мысленных различений Е, требуемых для порождения программы, должно задаваться выражением

Е = (2).

Более глубокий смысл уравнения работы при использовании выведенного ранее уравнения имеет вид:

L = V */ V, (2а)

где V * - общая работа на весь объём программы.

После подстановки (2а) во (2) получим:

Е = . (3)

Уравнение (3) показывает, что мысленная работа по реализации любого алгоритма с данным потенциальным объёмом в каждом языке пропорционально квадрату объёма программы. Т.к. “квадрат суммы больше суммы квадратов“, то правильное разбиение на модули может уменьшить работу по программированию реализаций, разбитых на отдельные части.

Теперь необходимо проверить уравнение работы (2) с практической точки зрения. Для разработки эксперимента перейдём от подсчёта элементарных мыслительных различений к измерению времени.