数据结构如何将复杂度从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<int>&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<int>&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<int>&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<int>&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)的目标。如果你还是不太明白，我的经验是要不断地归纳总结，总是会有一点收获的。

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。