我在spoj上尝试this问题。
首先,我想出了一种简单的o(blogb)算法(将问题代入b)。但是由于问题的作者提到了约束,因为b属于[0,10 ^ 7],所以我不敢相信无论如何,无论如何我都将其编码如下
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#define PR(x) cout<<#x"="<<x<<endl
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(long long i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(long long i=0;i<n;i++)printf(#x"[%d]=\t%d\n",i,x[i])
using namespace std;
#include <stdio.h>
struct node {
int val;
int idx;
};
bool operator<(node a,node b){ return a.val<b.val;}
node contain[10000001];
int main(){
int mx=1,count=1,t,n;
scanf("%d",&t);
while(t--){
count=1;mx=1;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&contain[i].val);
contain[i].idx=i;
}
sort(contain,contain+n);
for(int j=1;j<n;j++){
if(contain[j].idx>contain[j-1].idx)
count++;
else count=1;
mx=max(count,mx);
}
printf("%d\n",n-mx);
}
}
并且它在SPOJ服务器上经过了0.01秒(已知速度很慢)
但是我很快想出了O(b)算法,代码如下
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#define PR(x) printf(#x"=%d\n",x)
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf(#x"[%d]=\t%d\n",i,x[i])
using namespace std;
int val[1001];
int arr[1001];
int main() {
int t;
int n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int mn=2<<29,count=1,mx=1;
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
if(arr[i]<mn) { mn=arr[i];}
}
for(int i=0;i<n;i++){
val[arr[i]-mn]=i;
}
for(int i=1;i<n;i++){
if(val[i]>val[i-1]) count++;
else {
count=1;
}
if(mx<count) mx=count;
}
printf("%d\n",n-mx);
}
}
但令人惊讶的是,它花了 0.14s :O
现在我的问题是,对于b> 2 , o(b)是否比o(blogb)好?那为什么时间差那么大呢?社区中的一位成员建议这可能是由于缓存未命中所致。o(b)代码与o(blogb)相比本地化程度较低,但我不认为这会导致 0.10s 的差异
编辑:我看到所有答案都趋向于以渐进表示法隐藏的常量值,这些值通常会导致算法运行时出现差异。但是,如果您看一下代码,您将意识到我正在做的就是替换对排序的调用现在我假设sort至少一次访问数组的每个元素,如果我们考虑执行的行数,这是否会使两个程序更接近?此外,我过去使用spoj的经历告诉我的I / O会对程序的运行时间产生巨大的影响,但是我在两个代码中都使用了相同的I / O例程。
最佳答案
大O符号表示当输入集接近无限大小时函数需要花费多长时间。如果您有足够大的数据集,则O(n)将始终胜过O(n log n)。
实际上,由于大O公式中的其他隐藏变量,某些“性能较差”的算法更快。一些更具可扩展性的算法可能会更慢。随着输入集的变小,差异变得更加任意。
当我花费数小时来实现可伸缩解决方案时,以及在进行测试时,我都以艰辛的方式学习了所有这些方法,发现这只会对大型数据集更快。
编辑:
关于特定情况,有人提到同一行代码在性能方面可能有很大差异。这可能是这种情况。这意味着大O公式中的“隐藏变量”非常相关。您越了解计算机内部的工作原理,就会掌握更多的优化技术。
如果您只记得一件事,请记住这一点。请勿仅通过阅读代码来比较两种算法的性能。如果那么重要,请在实际数据集上安排一个实际的实现。
关于c++ - O(n)比O(nlogn)需要更多时间,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10338585/