Я написал псевдокод для метода вычисления записи в строке i, col j треугольника Паскаля.Время выполнения рекурсивного метода
Pascal(i,j)
if(i==j or j==0)
return 1;
return Pascal(i-1,j-1) + Pascal(i-1,j)
Моя проблема в том, что я не могу определить время работы. Я знаю, что это экспоненциально, но я не знаю, как это доказать, решая рекуррентное отношение.
Вы бы хорошо разработали несколько примеров, чтобы увидеть, как далеко назад вы идете. Помните, что у вас есть треугольник. Вы начинаете с строки i, тогда вы в строке i-1. На следующем шаге вы находитесь в строке i-2. И т. Д. Сколько строк назад вы должны идти в худшем случае?
Нарисуйте картинку и сделайте примеры, чтобы построить интуицию. Найти доказательство из нескольких примеров с i = 6 должно быть довольно легко.
Я сделал именно это, и мне показалось, что для получения значений для строки n требуется количество добавлений в предыдущей строке плюс n-1. Итак, я получаю T (n) = T (n-1) + n-1. Это верно? – user1317750
Похоже, что у вас могут быть некоторые ошибки в вашем коде: в if, вы устанавливаете j в 0, а не используете '=='. Кроме того, вы возвращаете только 1 - где return, если i! = 0 и j! = 0? –
Я предлагаю задать ваш вопрос в MathOverflow –