В книге излагаются основные (начальные) разделы теории сложности алгоритмов. Различаются алгебраическая и битовая сложности, каждая из которых рассматривается в худшем случае и в среднем. Ряд основных понятий теории сложности, как-то: оценки снизу и сверху, нижняя граница сложности алгоритмов некоторого класса, оптимальный алгоритм и т.д., рассматривается не только в обычном функциональном, но и в асимптотическом смысле: асимптотические оценки, асимптотическая нижняя граница, оптимальность по порядку сложности и т. д. Показывается, что при исследовании существования алгоритма решения задачи, имеющего "не очень высокую" сложность, важную роль может играть сводимость одной задачи к другой. Изложение сопровождается анализом сложности большого числа алгоритмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др. Для студентов, специализирующихся в области математики и информатики.
V knige izlagajutsja osnovnye (nachalnye) razdely teorii slozhnosti algoritmov. Razlichajutsja algebraicheskaja i bitovaja slozhnosti, kazhdaja iz kotorykh rassmatrivaetsja v khudshem sluchae i v srednem. Rjad osnovnykh ponjatij teorii slozhnosti, kak-to: otsenki snizu i sverkhu, nizhnjaja granitsa slozhnosti algoritmov nekotorogo klassa, optimalnyj algoritm i t.d., rassmatrivaetsja ne tolko v obychnom funktsionalnom, no i v asimptoticheskom smysle: asimptoticheskie otsenki, asimptoticheskaja nizhnjaja granitsa, optimalnost po porjadku slozhnosti i t. d. Pokazyvaetsja, chto pri issledovanii suschestvovanija algoritma reshenija zadachi, imejuschego "ne ochen vysokuju" slozhnost, vazhnuju rol mozhet igrat svodimost odnoj zadachi k drugoj. Izlozhenie soprovozhdaetsja analizom slozhnosti bolshogo chisla algoritmov arifmetiki, sortirovki i poiska, vychislitelnoj geometrii, teorii grafov i dr. Dlja studentov, spetsializirujuschikhsja v oblasti matematiki i informatiki.
