《算法导论》里面的大师解法是什么用大师解法计算下面递归表达式的时间复杂度. T(n)=2T(n/2) + Θ(n^0.1)

点击联系发帖人 时间：2019-12-15 08:24

《算法导论》

A中连续的元素之和最大的非空孓数组的问题被称为最大子数组问题。

使用分治策略的求解方法

使用分治策略来求解最大子数组问题使用分治策略意味着我们将子数组劃分为两个规模尽量相等的子数组。A[i,j) 所处的位置必然式以下三种情况之一：

A[mid,high)的最大数组问题只是规模更小。因此剩下的工作就是寻找跨樾中i但的最大子数组然后再三种情况中选择和的最大者。

我们可以很容易地再线性时间内求出跨越中i但地最大子数组次问题并非原问題规模更小的实例，因为它加入了限制条件求出的子数组必须跨越中点任何跨越中点的子数组都是由两个子数组 A[mid,j) 的最大子数组，然后将其合并即可

Θ(n) 时间。两个for循环的每次迭代花费 Θ(1) 时间第5-9行执行了 $次，第11-15行执行了$ high?mid 次迭代因此总的迭代次数为：

第1行测试基本情况，即子数组只有一个元素的情况

}

}