我在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/

10-11 23:01
查看更多