1

このトピックについて以前に行ったこと:

私はかなり長い間、このトピックに固執してきました。「Algorithms in Java」と Adam Drozdek の本で単純なアルゴリズムの複雑さを計算する例をいくつか読み、フォーラムを検索しましたが、この質問が見つかりませんでした。

問題：

「Algorithms in Java」などの一部の書籍では、アルゴリズムの時間計算量を計算するために、特定のステートメントを n としています。しかし、「Adam Drozdek」の別の本では、ループの実行回数を n としています。したがって、1 つの n を使用して複雑さを計算すると、別の本では n が別のものとして扱われるため、計算された複雑さが間違っています。例を以下に示します。では、どうすれば同じプログラムの複雑さについて普遍的に合意できるのでしょうか?

例

順次検索の例があります。これがコードです。

static int search(int a[], int v, int l, int r)   { 
    int i;     
    for (i = l; i <= r; i++)       
        if (v == a[i]) return i;     
    return -1;
} `

最悪のケースを考慮して：

r を n に等しいとしました。したがって、ループは n 回実行されます...

1) 比較とインクリメントと比較が n 回実行されるため、3n になります。

2) 初期化と宣言と return -1 が 1 回実行されるため、3 回です。

したがって、方程式は次のようになります

3n+3 で、複雑さは O(n) です。しかし、本はノーを考慮しています。n として比較の

4

4 に答える 4

0

「複雑さ」という用語（および用語の過負荷）が混乱を引き起こしているようです。

は3n + 3、プログラムの複雑さをより正確に表したものです。しかし、コンピューター サイエンスでは、(a) big-O の複雑さがはるかに重要であり、(b) big-O の複雑さが同じ場合、3nvsまたは "+ 3" と "+ 0"を気にすることはほとんどありません。 n、アルゴリズムを区別するために他の多くの要因が関係します。たとえば、「+ 3」ステートメントは、その実行内容に応じて、それぞれ非常にコストのかかる操作または安価な操作になる可能性があります。そのような場合、テスト中のコードまたはライブ プロダクションのタイミングを実際に測定すると、同じ Big-O の複雑さを持つアルゴリズムを比較したときに、より良い結果が得られます。

アルゴリズムの複雑さについて議論するとき、これらの定数を気にすることはめったにないため、複雑さという用語をアルゴリズムのビッグオーの複雑さと交換することがよくあります。

ちなみに、nはアルゴリズムの反復回数を駆動する入力値です。それ以外は、実際には何でもかまいません。プログラム内の実際の変数に限定されません。たとえば、ファイルからの入力の読み取りをループするプログラムは、ファイルnから読み取られた入力の数を = とします。

于 2013-09-07T08:03:31.690 に答える
0

スティーブンがすでに述べたように、重要なのはスケーリングと、アルゴリズムがそのスケーラブルなエンティティをどのように使用するかです。

あなたの例を引用する：

static int search(int a[], int v, int l, int r)   { 
    int i;     
    for (i = l; i <= r; i++)       
        if (foo(a)) return something;     
    return -1;
}

比較でスケーラブルなエンティティ、つまり配列を使用して何らかの決定を下す場合、その特定の値が複雑さの原因になります。

同様に、スケーラブルなエンティティに関係なく、比較関数で同じ量の計算を行っている場合、それは貢献しません。たとえば、関数 foo が常に使用する場合、そのジョブを実行するために 5 台のマシンの命令が必要になる場合、それは基本的に一定の操作です。

あなたの場合、比較は毎回単一の操作であるため、O(n) の複雑さは変わりません。

于 2013-09-07T08:01:43.667 に答える