数据结构如何将复杂度从O(n^3)杀到O(n)
数据结构如何将复杂度从O(n^3)杀到O(n)，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
最近在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)的目标。如果你还是不太明白，我的经验是要不断地归纳总结，总是会有一点收获的。
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注行业资讯频道，感谢您对的支持。
