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