用手机做网站的流程,兰州app定制,个人网站建设免费主机,商城网站开发视频递归算法时间复杂度的计算方程式一个递归方程#xff1a; 在引入递归树之前可以考虑一个例子#xff1a; T(n) 2T(n/2) n2 迭代2次可以得#xff1a; T(n) n2 2(2T(n/4) (n/2) 2) 还可以继续迭代#xff0c;将其完全展开可得#xff1a; T(n) n2 2((n/2) 2 2((n/2…递归算法时间复杂度的计算方程式一个递归方程 在引入递归树之前可以考虑一个例子 T(n) 2T(n/2) n2 迭代2次可以得 T(n) n2 2(2T(n/4) (n/2) 2) 还可以继续迭代将其完全展开可得 T(n) n2 2((n/2) 2 2((n/22)2 2((n/23) 2 2((n/24) 2 …2((n/2i) 2 2T(n/2i 1)))…)))) ……(1) 而当n/2i1 1时迭代结束。 将(1)式小括号展开可得 T(n) n2 2(n/2)2 22(n/22) 2 … 2i(n/2i)2 2i1T(n/2i1) 这恰好是一个树形结构由此可引出递归树法。 图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n2留在其中而将两个递归项T(n/2) T(n/2)分别摊给了他的两个子节点如此循环。 图中所有节点之和为: [1 1/2 (1/2)2 (1/2)3 … (1/2)i] n2 2n2 可知其时间复杂度为O(n2) 可以得到递归树的规则为 (1) 每层的节点为T(n) kT(n / m) f(n)中的f(n)在当前的n/m下的值 (2) 每个节点的分支数为k (3)每层的右侧标出当前层中所有节点的和。 再举个例子 T(n) T(n/3) T(2n/3) n 其递归树如下图所示 可见每层的值都为n从根到叶节点的最长路径是 因为最后递归的停止是在(2/3)kn 1.则 于是 即T(n) O(nlogn) 总结利用此方法解递归算法复杂度 f(n) af(n/b) d(n) 1.当d(n)为常数时 2.当d(n) cn 时 3.当d(n)为其他情况时可用递归树进行分析。 由第二种情况知若采用分治法对原算法进行改进则着重点是采用新的计算方法缩小a值。
