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

Упражнение

о 2.51 Известно, что временная сложность одной задачи равна 7V logTV, а другой - N. Что данное утверждение неявно выражает об относительной производительности определенных алгоритмов, которые решают эти задачи?

Ссылки к части 1

Существует множество вводных учебников по программированию. Стандартной ссылкой на язык С++ является книга Страуструпа (Stroustup), а наилучшим источников знаний о С с примерами программ, многие из которых являются полноценными профаммами также для С++ и написаны в том же духе, что и профаммы в этой книге, служит книга Кернигана и Ричи (Kemigan, Ritchie) о языке С.

Несколько вариантов алгоритмов для задачи union-find из главы 1 собраны и объяснены в статье Ван-Левена и Тарьяна (van Leewen, Tarjan).

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

Классическая работа по анализу алгоритмов, основанная на измерениях асимптотической низкой производительности - это книга Ахо, Хопкрофта и Ульмана (Aho, Hopcroft, Ullman). Книги Кнута (Knuth) покрывают анализ средней производительности более полно и являются официальным источником определенных свойств многих алгоритмов. Книги Тонне, Баэ-Ят (Gonnet, Baez-Yates) и Кормен, Лейзерсон, Ривест (Cormen, Leisorson, Rivest) являются более современными работами. Обе они включают обширный список ссылок на исследовательскую литературу.

Книга Грэм, Кнут, Паташник (Graham, Knuth, Patshnik) рассказывает об областях математики, которые обычно встречаются при анализе алгоритмов; этот же материал разбросан и в упомянутых ранее книгах Кнута. Книга Седжвика и Флажоле представляет собой исчерпывающее введение в предмет.

A. V. АНО, J. Е. HOPCROFT, AND J. D. ULLMAN, The Design and Analysis of Algorithms, Addison-Wesley, Reading, MA, 1975.

J. L. Bentley, Programming Pearls, Addison-Wesley, Reading, MA, 1985; More Programming Pearls, Addison-Wesley, Reading, MA, 1988.

R. Baeza-Yates and G. H. Gonnel, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading,MA, 1984.

T. H. Gormen, G. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press/ McGraw-Hill, Gambridge, MA, 1990.

R. L. GRAHAM, D. E. KNUTH, AND O. PATASHNIK, Concrete Mathematics, Addison-Wesley, Reading, MA, 1988.

B. W. Kernighan and D. M. Ritchie, The С Programming Language, second edition, Prentice-Hall, Englewood Cliffs, NJ, 1988.

D. E. Kjiuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, third edition, Addison-Wesley, Reading, MA, 1997; Volume 2: Seminumerical Algorithms, third edition, Addison-Wesley, Reading, MA, 1998; Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading,MA, 1998.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

B. Stroustrup, The С++ Programming Language, third edition, Addison-Wesley, Reading MA, 1997.

J. van Leeuwen and R. E. Tarjan, Worst-case analysis of set-union algorithms, Journal of the ACM, 1984.