Чтобы вычислить функцию времени выполнения алгоритма в худшем случае, какие шаги необходимо выполнить? Алгоритмы

Question

Чтобы вычислить функцию времени выполнения алгоритма в худшем случае, какие шаги необходимо выполнить?Пожалуйста, кто-нибудь направит меня в этом.Я думаю, что эти шаги включают в себя некоторые математические доказательства.Если я прав В каких областях математики я должен быть сильным?(Я думаю, математическая индукция, функции, наборы достаточно)

Спасибо

Answer 1

Хорошие ответы вы найдете в следующих книгах:

• http://www.algorist.com/
• "Искусство компьютерного программирования", Кнут

Я думаю, что в основном это: хорошее понимание алгоритма, комбинаторика и теория вычислительной сложности - http://en.wikipedia.org/wiki/Computational_complexity_theory

Answer 2

Чтобы узнать о вычислительной сложности, вам нужно знать Исчисление, Комбинаторику, Теорию множеств, Суммирование среди других тем по математике.

Хорошая книга; хотя довольно теоретическим является Введение в алгоритмы по Cormen et. и др.