В качестве книги с доказательствами, написанной для студентов и аспирантов, я настоятельно рекомендую Introduction to Algorithms1 («Алгоритмы. Вводный курс») Кормена (Cormen), Лейзерсона (Leiserson), Ривеста (Rivest) и Стейна (Stein) (этих авторов обычно объединяют под аббревиатурой CLRS).
Во многих случаях возможность свести постановку задачи к эквивалентной задаче для определенного класса графов дает полезную информацию о том, насколько сложно ее решить.
Некоторые задачи класса NP называются NP-сложными; NP-сложная задача (несколько рекурсивно) определяется как любая задача, которая по крайней мере столь же сложна, как и самая сложная задача класса NP
что, если бы для произвольного объекта у нас была функция, которая бы принимала ключ этого объекта и преобразовывала его в индекс массива, так что мы бы точно знали, где находится объект? Именно так работают хеш-таблицы. Первая часть хеш-таблицы — это хеш-функция; она преобразует ключ элемента, который помещается в хеш.
Связный список — это структура данных, в которой каждый элемент содержит данные и указатель на следующий элемент списка (а если это двусвязный список, то также ссылку на предыдущий элемент)
точки зрения математики мы вычисляем асимптотическое время выполнения алгоритма, то есть скорость увеличения времени выполнения в зависимости от размера входных данных.
