O(nlog2为底n怎么算n)和O(nlogn)是一个意思吗

来源：蜘蛛抓取(WebSpider) 时间：2016-11-30 17:25 标签： log2为底n怎么算
时间复杂度的区别测评！O(n)、O(nlogn)、O(n^2)、O(n^3)以最长子段和为例 - 编程当前位置:& &&&时间复杂度的区别测评！O(n)、O(nlogn)、O(n^2)、O(时间复杂度的区别测评！O(n)、O(nlogn)、O(n^2)、O(n^3)以最长子段和为例&&网友分享于：&&浏览：20次时间复杂度的差异测评！O(n)、O(nlogn)、O(n^2)、O(n^3)以最长子段和为例时间复杂度的差异测评
大家都知道，判断一个算法够不够好，一个很重要的标准就是算法的时间复杂度&，同样一个问题，不同的算法执行的时间差异可以很大！这个就是时间复杂度导致的，关于时间复杂度的定义等，本菜鸟不予说明，大家可以参考各大算法或者数据结构书籍，里面有详细的解释，今天给大家带来的是不同时间复杂度算法运行时间的差异！
测试题目：
输入一个数据n（0,1000000），然后输入n个数据（-），求出最长子段和。
样例输入：
-1 5 6 -3 7
样例输出：
题目分析：这是一个很经典的DP问题，大部分人都知道，这里将分别用O(n^3)、O(n^2)、O(nlogn)、O(n)算法求解。
O(n^3)算法：
这是一个很容易想到的算法（PS：当初我还没想出来。。。）。该算法使用3重循环，将所有子段的和求出，然后求出和最大的。
代码如下：
#include &cstdio&
#include &algorithm&
#define INF 0x3f3f3f3f
#define MAX 101
int a[MAX];
int main(int argc, char const *argv[])
freopen(&test.in&,&r&,stdin);
for(int i=0; i&MAX; i++){
scanf(&%d&,&a[i]);
int ans = -INF;
for(int i=0; i&MAX; i++){
for(int j=i; j&MAX; j++){
int sum = 0;
for(int k=i; k&=j; k++)
sum += a[k];
ans = max(ans,sum);
printf(&%d&,ans);
O(n^2)算法：
这个算法用了一点数学知识，可以使用两重循环达到同样的效果。用s[i]储存前i-1个子段的和，然后使用两重循环用s[j]-s[i]求出所有子段的和，然后求出其中最大的。
代码如下：
#include &cstdio&
#include &algorithm&
#define INF 0x3f3f3f3f
#define MAX 101
int a[MAX],s[MAX+1];
int main(int argc, char const *argv[])
freopen(&test.in&,&r&,stdin);
for(int i=0; i&MAX; i++){
scanf(&%d&,&a[i]);
s[i+1] = s[i]+a[i];
int ans = -INF;
for(int i=0; i&MAX; i++){
for(int j=i+1; j&=MAX; j++){
ans = max(ans, s[j]-s[i]);
printf(&%d&,ans);
O(nlogn)算法：
改算法使用的思想是分治法思想，即将一个大问题化成无数个小问题，无数个小问题的最优解得出来的就是大问题的最优解。用分治法将数组分为两部分，那么最长子串和只可能有三种情况，在左边、在右边、一部分在左边，一部分在右边。然后继续递归，即可求出解。
代码如下：
#include &cstdio&
#include &algorithm&
#define INF 0x3f3f3f3f
#define MAX 101
int a[MAX];
int max_sum(const int &l, const int &r){ //l为左端点，r为右端点
int l_max, r_max, lm_max, rm_max, m_max, tmp,
if(l == r){
return a[l];
m = (l+r)&&1; //m为l和r的中点
l_max = max_sum(l, m);
//如果最长子段和在左边，l_max为和
r_max = max_sum(m+1,r);
//如果最长子段和在右边，r_max为和
/*如果一半在左边，一半在右边*/
lm_max = -INF, tmp = 0;
for(int i=m; i&= i--){
//lm_max代表从中间到左边的最长子段和
lm_max = max(lm_max, tmp+=a[i]);
rm_max = -INF, tmp = 0;
for(int i=m+1; i&=r; i++){
//rm_max代表从中间到右边的最长子段和
rm_max = max(rm_max, tmp+=a[i]);
return max(max(l_max, r_max), lm_max+rm_max); //返回最长子段和
int main(int argc, char const *argv[])
freopen(&test.in&,&r&,stdin);
for(int i=0; i&MAX; i++){
scanf(&%d&,&a[i]);
printf(&%d&,max_sum(0,MAX-1));
O(n)算法：
这个算法应该就是这道题的最优解，使用动态规划进行求解。由这道题能得出一个动态规划方程：s[i] = max(s[i-1], s[i-1]+a[i])，即比较前i-1个子段和和前i个子段的大小，然后选取最大的。这里还要知道一件事，如果最长子段和等于小于0了，那么最长子段和重新计算。
代码如下：
#include &cstdio&
#include &algorithm&
#define INF 0x3f3f3f3f
#define MAX 101
int a[MAX];
int main(int argc, char const *argv[])
int temp = 0;
freopen(&test.in&,&r&,stdin);
for(int i=0; i&MAX; i++){
scanf(&%d&,&a[i]);
int ans = -INF;
for(int i=0; i&MAX; i++){
if(temp+a[i] & 0){
ans = max(ans, temp+=a[i]);
printf(&%d&,ans);
测试算法所用时间：
这里使用的数据为随机生成的大小为（-）的数据。
一百个数据：
从上面的数据结果我们发现，所有算法的时间没什么差异，甚至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)！
测试总结：
根据上面结果，我绘制了以下表格：
第一列为时间复杂度，第一行为数据个数，中间数据为时间（秒为单位）。
----------
现在我们可以发现了吧，一个好的算法有多么的重要！！所以大家一定要好好学习算法，这个才是编程的精髓所在！！！
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有

我要回帖

更多关于 log2为底n怎么算 的文章

 

随机推荐