递推关系17 Mar 2025 | 阅读 2 分钟 递归是一种用较小输入的值来描述函数的方程或不等式。解决递归关系意味着获得一个在自然数上定义的函数，该函数满足递归关系。 例如，MERGE SORT 过程的最坏情况运行时间 T(n) 由递归关系描述。 T (n) = θ (1) if n=1 2T 有四种解决递归关系的方法 1. 代入法代入法包括两个主要步骤
例如 1 用代入法解方程。 T (n) = T 我们必须证明它被渐进地限制在 O (log n) 内。 解决方案 For T (n) = O (log n) 我们必须证明对于某个常数 c 将其代入给定的递归方程。 T (n) ≤c log 例 2 考虑递归 T (n) = 2T 找到 T 的渐进界限。 解决方案 We guess the solution is O (n (logn)).Thus for constant 'c'. T (n) ≤c n logn Put this in given Recurrence Equation. Now, T (n) ≤2c 2. 迭代法这意味着展开递归并将其表示为 n 和初始条件项的总和。 例 1： 考虑递归 解决方案
T (n) = 2T (n-1)
= 2[2T (n-2)] = 22T (n-2)
= 4[2T (n-3)] = 23T (n-3)
= 8[2T (n-4)] = 24T (n-4) (Eq.1)
Repeat the procedure for i times
T (n) = 2i T (n-i)
Put n-i=1 or i= n-1 in (Eq.1)
T (n) = 2n-1 T (1)
= 2n-1 .1 {T (1) =1 .....given}
= 2n-1
例 2： 考虑递归 解决方案 T (n) = T (n-1) +1
= (T (n-2) +1) +1 = (T (n-3) +1) +1+1
= T (n-4) +4 = T (n-5) +1+4
= T (n-5) +5= T (n-k) + k
Where k = n-1
T (n-k) = T (1) = θ (1)
T (n) = θ (1) + (n-1) = 1+n-1=n= θ (n).
下一主题递归树方法 |
我们请求您订阅我们的新闻通讯以获取最新更新。
我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Python
Java
JavaScript
SQL
C
C++
HTML
CSS
React
Node.js
Spring Boot
C#
PHP
MySQL
MongoDB
AI
ML
DSA
DBMS
OS
Aptitude
Reasoning
+ θ (n) if n>1
