时间复杂度的差异测评！O(n)、O(nlogn)、O(n^2)、O(n^3)以最长子段和为例

时间复杂度的差异测评前言：大家都知道，判断一个算法够不够好，一个很重要的标准就是算法的时间复杂度 ，同样一个问题，不同的算法执行的时间差异可以很大！这个就是时间复杂度导致的，关于时间复杂度的定义等，本菜鸟不予说明，大家可以参考各大算法或者数据结构书籍，里面有详细的解释，今天给大家带来的是不同时间复杂度算法运行时间的差异！
测试题目：输入一个数据n（0,1000000），然后输入n个数据（-1000,1000），求出最长子段和。样例输入：5-1 5 6 -3 7
样例输出：15
题目分析：这是一个很经典的DP问题，大部分人都知道，这里将分别用O(n^3)、O(n^2)、O(nlogn)、O(n)算法求解。
O(n^3)算法：这是一个很容易想到的算法（PS：当初我还没想出来。。。）。该算法使用3重循环，将所有子段的和求出，然后求出和最大的。代码如下：

从上面的数据结果我们发现，所有算法的时间没什么差异，甚至O(n)算法时间要长。不要急，接着往下看！一千个数据：

这下我们发现不同了吧，O(n^3)算法的时间为其他时间的30多倍。。。。。  O(n^3)完败！。。不过其他算法还未分出胜负，咱们接着比。一万个数据：

这时候O(n^3)已经运行不出来了。。O(n^2)也被甩了一大截。。。还有两个兄弟没分出胜负，咱们继续：十万个数据：

这时候O(n^2)也运行不出来了。。O(n)小胜。。百万个数据：
1000000的数据量，O(n)已经比O(nlogn)快了将近一倍，这下冠军已经产生了！O(n)！
测试总结：根据上面结果，我绘制了以下表格：第一列为时间复杂度，第一行为数据个数，中间数据为时间（秒为单位）。
 
100
1000
10000
100000
1000000
O(n)
0.035
0.034
0.041
0.049
0.339
O(nlogn)
0.028
0.023
0.032
0.069
0.580
O(n^2)
0.025
0.026
0.357
--------
----------
O(n^3)
0.023
0.655
------
--------
---------

现在我们可以发现了吧，一个好的算法有多么的重要！！所以大家一定要好好学习算法，这个才是编程的精髓所在！！！

1楼NO_ERROR32昨天 16:03
[code=cpp]nif（body == “发烧”）n{n      printf("大神求破");n}n[/code]