大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
数据结构如何将复杂度从O(n^3)杀到O(n),很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
网站制作、建网站找专业网络公司创新互联建站:定制网站、模板网站、仿站、微信小程序定制开发、软件开发、app软件开发等。做网站价格咨询创新互联建站:服务完善、10年建站、值得信赖!网站制作电话:13518219792
最近在LEETCODE上刚好做到这一道题(53.Maximum Subarray)。突然想到数据结构中也有这道题目的例子,于是起兴来个总结。
题目: 给你一个数组,让你求出其中最大的子序列之和。
如:输入[-2,1,-3,4,-1,2,1,-5,4],其最大的子序列之和为6([4,-1,2,1]).
PS:还记得时间复杂度怎么计算的吗?
以最坏的情况为基准,数量级至上。嵌套相乘,同级相加。
可能需要说明的函数/定义:
max(a,b) : 返回a,b中较大的那一个。
vector
&nums : 传入一个vector库,若你对它很陌生,可以暂时把它看做数组(当然它和数组有区别)。
以下所有代码均只有函数部分。
完整代码可在: https://github.com/Ckend/GongZhongHao/tree/master/2.27 中查看。
O(n^3)
首先,最直接的思维是将每一个子序列的和都求出来。temp的作用是:1.求每个子序列的和,2.每次求完都会和result对比,如果比result大,则将值赋给result。每次这两个操作结束,temp都会清零。
int MaxSubSequenceSum(std::vector
&nums){ int temp = 0 , result = 0;
for (int i = 0 ; i < nums.size(); ++i) {
for (int j = i; j < nums.size(); ++j) {
temp = 0;
for (int k = i; k <= j; ++k) {
temp += nums[k];
result = std::max(result, temp);
}
}
}
return result;
}
这个算法是绝对正确的。但是效率非常低下。演示如下:
演示并未展现出全部的可能(或许也有点不太准确,最后黄色部分不应该和紫色部分共同前进),但是就如同紫色部分,所有的子序列都会被检测一遍。
我们会思考是否没必要使用三个循环,也许两个循环就够了?
我们从上图看到,其实FOR2和FOR3都可以进行这种筛选最大子序列的操作,因为他们的行进轨迹其实都是一样的。于是或许可以删掉那一个多余的循环。
O(n^2)
int MaxSubSequenceSum(std::vector
&nums){ int temp = 0, result = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i; j < nums.size(); ++j) {
temp += nums[j];
result = std::max(result, temp);
}
temp = 0;
}
return result;
}
虽然说O(n^2)是一个比较可以接受的复杂度。但是如果我们想要更加优化的算法。可能就要往抽象领域里延伸了。
这个O(n)的算法仅仅七行代码,但是想要理解清楚可没那么简单。我们可以从中看出,它与O(n^2)算法的最大区别在于,少了一个循环,并且temp = 0 被 temp = std::max(0, temp) 代替。
为什么我们在O(n^2)的算法中需要两次循环?因为我们需要把temp清零以保存下一轮的最大值。但是如果我们舍弃这一步操作呢?当序列中全是正数的时候,毋庸置疑,最大子序列就是它自身,于是我们只需要讨论两种情况:
1.序列中有一个以上的正数
当序列中只有一个正数的时候,自然,子序列就是那一个正数。
当序列有大于两个正数的时候,我们可以确定,最大子序列一定大于0。所以当temp的合小于零的时候,我们可以确定这条序列绝对不是最大子序列,于是将它清零,否则temp不清零。直到遇到真正的最大子序列。
2.序列中全是负数
如果序列中全是负数,那么最大子序列肯定只有一个数。利用result = std::max(result, temp);可以直接判断出来。
O(n)
int MaxSubSequenceSum(std::vector
&nums){ int temp = 0, result = nums[0];
for (int i = 0; i < nums.size(); ++i) {
temp += nums[i];
result = std::max(result, temp);
temp = std::max(0, temp);
}
return result;
}
于是通过这种巧妙的方法,我们成功实现了将算法复杂度优化到O(n)的目标。如果你还是不太明白,我的经验是要不断地归纳总结,总是会有一点收获的。
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注创新互联行业资讯频道,感谢您对创新互联的支持。