Когда я только начинала заниматься искусственным интеллектом, многое для меня, человека с классическим математическим образованием, было совершенно непонятно.
Некоторые термины теории алгоритмов вызывали едва не священный трепет.
Когда кто-то рядом произносил "NP-полнота", я даже приблизительно не могла представить, о чем идет речь.
Вообще, классы сложности алгоритмов — удивительно интересная вещь.
Вот, дам ссылку на статью.
www2.computerra.ru/xterra/253871/
Статья написана очень хорошо, но лично мне понятны там не все логические переходы.
Постараюсь рассказать об этом попроще, а кроме того, надеюсь, расскажу и о других классах сложности алгоритмов.