O(n)比O(nlogn)花费更多时间

Question

我在spoj上尝试这个问题.首先,我提出了一种简单的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.14秒:O

现在我的问题是,对于b> 2,o(b)不比o(blogb)好吗？那么为什么时间差异如此之大？来自社区的一位成员表示,这可能是由于缓存未命中.与o(blogb)相比,o(b)代码的本地化程度较低.但是我没有看到导致0.10s的差异对于<1000运行代码？(是的b实际上小于1000.不知道为什么问题设定者夸大了这么多)

编辑:我看到所有答案都朝向渐近符号中的隐藏常量值,这些常常会导致算法运行时间的差异.但是如果你看一下代码,你会发现我正在做的就是用另一个遍历替换调用来排序现在我假设排序访问数组的每个元素至少一次.如果我们考虑执行的行数,那么这两个程序是否更接近？除了是,我过去使用spoj的经历告诉我I/O对程序的运行时间产生了极大的影响,但我在两个代码中都使用了相同的I/O例程.

Answer 1

Big O表示法描述了当输入集接近无限大小时函数需要多长时间.如果您有足够大的数据集,O(n)将始终超过O(n log n).

在实践中,由于大O公式中的其他隐藏变量,一些"性能较差"的算法更快.一些更可扩展的算法可能更慢.随着输入集变小,差异变得更加随意.

当我花费数小时实现可扩展的解决方案时,我学到了所有这些,并且在测试时发现它对于大型数据集来说只会更快.

编辑:

关于具体情况,有些人提到同一行代码在性能方面可能有很大差异.这可能就是这种情况.这意味着大O公式中的"隐藏变量"非常相关.您越了解计算机内部的工作方式,您就越有优化技术.

如果你只记得一件事,请记住这一点.永远不要只通过阅读代码来比较两种算法的性能.如果这很重要,请在实际数据集上实际实施.