首页 > 试题广场 >

采用分治法计算最大子段和时间复杂度为（）

[单选题]

查看答案及解析

callmexss

分治法计算最大子段和的时间复杂度是O(nlogn)

假设问题规模即数组长度为n，那么：

第一次：[0, n/2], [n/2+1, n]，每一部分是n/2

第二次：[0, n/4], [n/4+1, n/2], [n/2+1, 3n/4], [3n/4+1, n]，每一部分是n/4

...

第i次：假设第i次每个问题都不可再分，则每一部分为 n / n = 1，共有n项，于是有2^i = n

解得i = logn，每一次分治的时间复杂度是O(n)，二者相乘得时间复杂度O(nlogn)

动态规划的时间复杂度是O(n)

答案应该选B

发表于 2017-12-27 15:42:17 回复(1)

shimianmaifu

for循环的时间复杂度是O(n)

但是分治法存在递归推式

T(n)=1 n=1

T(n)=2T(n/2)+n n>1

根据主定理求出的时间复杂性为O（nlon2n）

所以答案是B

发表于 2019-12-22 18:47:06 回复(0)

kilakila

D,采用分治法计算最大子段和，只需要遍历数组一遍，复杂度为O(n)

发表于 2017-11-04 10:35:47 回复(0)

提交观点

问题信息

分治复杂度

上传者：牛100

难度：

3条回答 165收藏 5432浏览

扫一扫，把题目装进口袋