Используя индукцию, чтобы доказать временную сложность функций

Question

Я хочу, чтобы узнать временную сложность этой функции с помощью индукции п (п) = 0, если п = 0

е (п) = е (п - 1) + 2n - 1, если n ≥ 1 Im, используя повторную замену метода, поэтому я нашел близкую форму для f (n)

f (n) = f (n - 1) + 2n - 1 = f (n-2) + 4n-4 = f (n-3) + 6n-8 .... = f (ni) + 2^in-d

, а затем, взяв i = ni, вышел с f (n) = f (0) + 2^(n + 1) -d и может заключить, что имеет временную сложность O (2^n), так как f (0) и d - все константы.

однако я нашел ответ должен быть O (N^2) и где я сделал не так

Answer 1

Вашей математика была неправа.

f(n) = f(n - 1) + 2n - 1 
f(n) = f(n - 2) + 4n - 4 
f(n) = f(n - 3) + 6n - 9 
... 
f(n) = f(n - i) + 2i n - i^2 

Когда я = п вас есть:

f(n) = f(n - n) + 2n n - n^2 
    = f(0) + (2 - 1) n^2 
    = n^2 

Следовательно, ф (п) О (п^2)

Однако вы ошибаетесь. Это не сложность времени функции, которая является O (n), так как это количество рекурсий, которое она имеет, это порядок функции, что означает, что «быстро он расходится». O (n^2) означает, что функция расходится с квадратичной скоростью.

Answer 2

Я не совсем понял вопрос. Сложность вычисления значения О (п), потому что вы можете просто сделать расчет, начиная с 0:

f(0) = 0 
f(1) = 0 + 2*1 - 1 = 1 
f(2) = 1 + 2*2 - 1 = 4 
f(3) = 4 + 2*3 - 1 = 9 

На самом деле, вы, вероятно, получите идею. , , n-е значение n^2. Я угадываю в контексте проблемы, что это то, на что они хотят получить ответ. Однако, чтобы вычислить это, кажется, O (n).