1

私はspojでこの問題を試していました。まず第一に、私はある種の自明な o(blogb) アルゴリズムを思いつきました (whats 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) 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) よりも優れているということではありませんか? では、なぜこれほどまでに時間差があるのでしょうか。コミュニティのメンバーの 1 人は、キャッシュ ミスが原因である可能性があると示唆しました。o(b) コードは、o(blogb) に比べてローカライズされていません。コードの実行？(はい、b は実際には 1000 未満です。なぜ問題設定者がそれほど誇張したのかわかりません)

EDIT ：すべての答えは、アルゴリズムの実行時間に格差を引き起こすことが多い漸近表記の隠された定数値に向かっていることがわかります。ループの.今、私はソートが配列の各要素に少なくとも1回アクセスすると仮定しています.実行される行数で考えると、両方のプログラムをさらに近づけませんか?もちろん、spojでの私の過去の経験はI/Oを教えてくれます.プログラムの実行時間に大きな影響を与えますが、両方のコードで同じ I/O ルーチンを使用しています。

4

5 に答える 5

5

Big O表記は、入力セットが無限のサイズに近づくときに関数がかかる時間を表します。十分な大きさのデータセットがある場合、O（n）は常にO（n log n）を上回ります。

実際には、ビッグオーの式に他の隠れた変数があるため、一部の「パフォーマンスの低い」アルゴリズムの方が高速です。いくつかのよりスケーラブルなアルゴリズムは遅くなる可能性があります。入力セットが小さくなると、差はより恣意的になります。

スケーラブルなソリューションの実装に何時間も費やし、テストしたところ、大規模なデータセットの場合にのみ高速になることがわかりました。

編集：

特定のケースに関して、同じコード行がパフォーマンスに関して非常に異なる可能性があると言う人もいました。これはおそらくここに当てはまります。これは、ビッグオーの式の「隠れた変数」が非常に関連していることを意味します。コンピューターが内部でどのように機能するかをよく理解すればするほど、より多くの最適化手法を身に付けることができます。

覚えていることが1つしかない場合は、これを覚えておいてください。コードを読むだけで2つのアルゴリズムのパフォーマンスを比較しないでください。それが重要な場合は、現実的なデータセットで実際に実装する時間を計ってください。

于 2012-04-26T17:51:07.280 に答える
4

I/O 操作 ( scanf()、printf()) が結果にバイアスをかけています。

これらの操作は非常に遅いことで有名であり、タイミングをとるときに大きな不一致を示します。I/O 操作を使用してコードのパフォーマンスを測定することはありません。ただし、それらの操作が測定しようとしている場合を除きます。

したがって、それらの呼び出しを削除して、もう一度やり直してください。

また、0.1 秒が非常に小さいことも指摘します。0.1 秒の差は、実行可能ファイルのロードとコードの実行準備にかかる時間に関係している可能性があります。

于 2012-04-26T17:50:48.493 に答える
3

Big-O 表記は、任意の値を代入できる数式ではありませんn。それは関数の成長nを無限大に向かって説明するだけです。

于 2012-04-26T17:50:19.077 に答える
1

これは、人が想像するよりも興味深い質問です。O（）の概念は便利ですが、一部の人が考えるほど便利であるとは限りません。これは、対数オーダーに特に当てはまります。代数的に、対数は実際にはゼロの次数を持ちます。つまり、log（n）/ n^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 に答える