Искусство программирования для Unix

между средним временем выполнения алгоритма и размерами его входных данных. Алгоритм O(1) выполняется за постоянное время. Алгоритм О(n) выполняется за время, которое можно вычислить по формуле: An + С, где А — некоторый неизвестный постоянный коэффициент пропорциональности, а С — неизвестная константа, представляющая время установки. Линейный поиск определенного значения в списке представляет собой алгоритм типа О(n). Алгоритм О(n²) выполняется за время An² плюс величина более низкого порядка (которая может быть линейной либо логарифмической или любой другой функцией ниже квадратичной). Поиск повторяющихся значений в списке (примитивным методом, без сортировки списка) является алгоритмом О(n²). Аналогично, алгоритмы порядка О(n³) имеют среднее время выполнения, вычисляемое по кубической формуле. Такие алгоритмы часто слишком медленны для практического применения. Порядок O (log n) типичен для поиска по дереву. Взвешенный выбор алгоритма часто может сократить время выполнения с O(п²) до О(log n). Иногда, когда требуется рассчитать использование алгоритмом памяти, можно заметить, что оно изменяется как O(1) или О(n), или O (n^²). Как правило, алгоритмы с использованием памяти О (n²) или более высокого порядка являются непрактичными.

109

Удвоение мощности в течение каждых 18 месяцев, обычно цитируемое в контексте закона Мура, подразумевает, что можно достичь 26% прироста производительности просто путем приобретения нового аппаратного обеспечения через 6 месяцев.

110

Термины, введенные здесь для обозначения проблем проектирования, происходят из устоявшегося жаргона хакеров, описанного в книге [66].

111

Разделение случайной и необязательной сложности означает, что рассматриваемые здесь категории не являются тем же, что сущность и случайность в очерке Фреда Брукса 'No Silver Bullet' [8], однако в философском смысле они имеют одинаковое происхождение.

112

Молодые читатели могут не знать, что раньше терминалы печатали (на бумаге и очень медленно).

113

http://plan9.bell-labs.com/sys/doc/sam/sam.html

114

Разработчиками Emacs были Ричард М. Столлмен (Richard М. Stallman) и Берни Гринберг (Bernie Greenberg). Первоначальный редактор Emacs был изобретением Столлмена, первая версия со встроенным языком Lisp была создана Гринбергом, а окончательная на сегодняшний день версия создана Столлменом на основе версии Гринберга. К 2003 году нет полного изложения истории разработки редактора, но эту тему освещает статья Гринберга 'Multics Emacs: The History, Design, and Implementation', которую можно найти в Web по ключевым словам.

115

http://www.cs.yorku.ca/~oz/wily

116

http://plan9.bell-labs.com/sys/doc/acme/acme.html

117

Подробности на странице <ftp://ftp.idiom.com/pub/compilers-list/free-compilers> (Список бесплатных компиляторов и интерпретаторов).

118

За пределами мира Unix этот прирост аппаратной производительности на три порядка в значительной мере затмевается соответствующим понижением производительности программ.

119

Серьезность данной проблемы подтверждается богатым сленгом, выработанным Unix-программистами для описания различных ее разновидностей: 'псевдонимная ошибка' (aliasing bug), 'нарушение выделенной области памяти' (arena corruption), 'утечка памяти' (memory leak), 'переполнение буфера'