Класс сложности алгоритма

Речь идет о классах N , P , NP ?
посмотри тут к примеру
http://nature.web.ru/db/msg.html?mid=1157083&uri=node13.html
Вообще мне кажется надо искать по словам типа автомат (машина) Тьюринга, формальные языки и т.д.
Термины могут быть не точны так как изучаю это на немецком. Могу поскать литературу , может что на русском найду

Теоретически речь видимо пойдет о решении проблемы с помошью машины Тьюринга и о анализи времени которое она на это затратит.

Если же речь идет об анализе времени работы алгоритма , (к примеру одного из вариантов сортировки quicksort , heapsort ) то тут надо смотреть в зависимости от размера массива в трех случаях : лучший , средний и худший. Нас както учили выводить формулу для суммы выполнения всех строк и ее приближения с помощью "О-большого".

http://www.ksu.ru/f9/bin_files/24.pdf посмотри еще тут вроде то что надо

 

можно еще и тут посмотреть: http://discopal.ispras.ru/lectures/course-ispras-mipt-1-students.pdf
и тут: http://it.kgsu.ru/TI_7/salg_001.html

 

Если честно, то меня ничего из ссылок не впечатлило. Около, но не совсем то. Скажем так, я не нашел в них какого-либо вменяемого упоминания о задачах типа 3-сочетание (сколько их там базовых, 6 ?) .
Ну и моя любимая тема "P=NP" не раскрыта.

Надо все же попробовать найти книгу "Вычислительные машины и труднорешаемые задачи". Авторы, если не изменяет память Гэри и Джонсон. Тхе бест в этом вопросе.