1

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

现在我的问题是o(b) 不是比 o(blogb) 更好 b > 2吗？那为什么时间差这么大？社区的一位成员建议这可能是由于缓存未命中。与 o(blogb) 相比，o(b) 代码的本地化程度较低。但我认为对于 <1000运行代码？（是的b实际上小于1000。不知道为什么问题设置者夸大了这么多）

编辑：我看到所有答案都指向渐近符号中的隐藏常数值，这通常会导致算法运行时间的差异。但是如果你查看代码，你会意识到我所做的只是用另一个遍历替换排序调用的循环。现在我假设 sort 至少访问数组的每个元素一次。如果我们考虑执行的行数，这不会使两个程序更接近吗？除了是的，我过去使用 spoj 的经验告诉我 I/O对程序的运行时间产生巨大影响，但我在两个代码中使用相同的 I/O 例程。

4

5 回答 5

5

大 O 表示法描述了当输入集接近无限大小时函数需要多长时间。如果你有足够大的数据集，O(n) 总是会超过 O(n log n)。

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

当我花了几个小时实施一个可扩展的解决方案时，我通过艰难的方式学到了所有这些，并且在测试时发现它只会对大型数据集更快。

编辑：

关于具体案例，有人提到同一行代码在性能方面可能会有很大差异。这很可能是这里的情况。这意味着大 O 公式中的“隐藏变量”非常相关。您越了解计算机的内部工作原理，您掌握的优化技术就越多。

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

于 2012-04-26T17:51:07.280 回答
4

I/O 操作 ( scanf(), printf()) 使结果产生偏差。

这些操作是出了名的缓慢，并且在计时时显示出很大的差异。你永远不能使用包含任何 i/o 操作来衡量代码的性能，除非这些操作是你想要衡量的。

所以，删除这些电话，然后再试一次。

我还要指出，0.1s 非常小。0.1s 的差异可能是指加载可执行文件和准备执行代码所花费的时间。

于 2012-04-26T17:50:48.493 回答
3

Big-O 表示法不是一个可以插入任意值的公式n。它仅将函数的增长描述n为无穷大。

于 2012-04-26T17:50:19.077 回答
1

这是一个比人们想象的更有趣的问题。O() 概念可能很有用，但并不总是像某些人想象的那么有用。对于对数阶尤其如此。在代数上，对数的阶数确实为零，也就是说 log(n)/n^epsilon 对于任何正的 epsilon 都会收敛。

比我们想象的更多的是，订单计算中的对数因素并不重要。

然而，肯德尔·弗雷是对的。对于足够大的数据集，O(n*log(n)) 最终会丢失。只是数据集可能必须非常大才能显示对数差异。

于 2012-04-26T17:51:06.727 回答
0

我在 SPOj 中查看了您的解决方案。我注意到您的 O(nlogn) 解决方案占用了 79M 内存，而 O(n) 占用了非常少量的内存，显示为 0K。我也查看了其他解决方案。我看过的大多数最快的解决方案都使用了大量的内存。现在我能想到的最明显的原因是std::sort()函数的实现。它实现得非常好，使您的解决方案速度惊人。对于 O(n) 解决方案，我认为它可能会很慢，因为if() {...} else {...}. 尝试将其更改为三元运算符，并让我们知道它是否有任何不同。

希望能帮助到你 ！！

于 2012-04-27T06:24:29.620 回答