6

私は 2 つのアルゴリズムの実行速度を比較しようとしていました。素数 (10,000 個の数) を出力する力ずくの C プログラムと、Sieve of Eratosthenes C プログラム (これも 10,000 個の素数) です。

ふるいアルゴリズムの測定実行時間は、0.744 秒でした。

ブルート フォース アルゴリズムの実行時間を測定したところ、0.262 秒でした。

しかし、エラトステネスのふるいアルゴリズムは総当たり法よりも効率的であると言われたので、より高速に実行されると思いました. したがって、私が間違っているか、プログラムに欠陥があります (これは疑います)。

したがって、私の質問は次のとおりです。予想とは逆の結果が得られたので、エラトステネスのふるいは実際に試行分割と比較して速度の面で効率の悪いアルゴリズムであることが証明されますか?

関連性があるかどうかはわかりませんが、Dev C++ コンパイラと Windows 7 を使用しています。

4

6 に答える 6

6

いいえ、実行経過時間はプラットフォームごとに異なるため、効率を測定するための標準ではありません。「アルゴリズムが 10 秒で実行された」と言っても、アルゴリズム自体に関する情報はほとんどまたはまったく得られません。それに加えて、環境仕様全体と同時に実行されている他のプロセスを一覧表示する必要があり、非常に面倒です。したがって、順序表記 (Big Oh、Little Oh、Omega など) が開発されました。

効率は通常、次の 2 つのサブセクションに分かれています。

  1. 時間効率。
  2. スペース効率。

... 1 つのアルゴリズムは非常に時間効率が良いかもしれませんが、空間的には非常に非効率的です。その逆が適用されます。アルゴリズムは、特定の入力に対して実行する必要がある命令の量をスケーリングする際の漸近的な動作に基づいて分析されますn。これは、PhD コンピューター科学者によって細心の注意を払って研究されている分野に関する非常に高レベルの説明です。ここで詳細を読むことをお勧めします。

Big Oh表記のリンクを添付していることに注意してください.姉妹表記はすべてそのWikipediaページから見つけることができ、通常はそこから始めるのが良いでしょう. 空間効率や時間効率の違いにも出てきます。

Big Oh を使用した時間効率の小さな応用:

Racket で次の再帰関数を考えてみましょう (私が知っていれば Python にあるでしょう -- 私ができる最高の疑似コードです):

(define (fn_a input_a)
  (cond
    [(empty? input_a) empty]
    [(empty? (rest input_a)) input_a]
    [(> (first input_a) (fn_a (rest input_a))) (cons (first input_a) empty)]
    [else (fn_a (rest input_a))]))

empty?... 、rest、>およびfirstはすべて O(1)であることがわかります。また、最悪の場合、 のfn_aの 3 番目の条件と 4 番目の条件で がrest呼び出されることにも注意してinput_aください。次に、再帰関係を T(n) = O(1) + 2T(n - 1) と書くことができます。これを再帰関係チャートで調べるとfn_a、最悪の場合、2 つの再帰呼び出しが行われるため、O(2^n) の順序であることがわかります。

fn_aまた、Big Oh の正式な定義により、それが O(3^n)であると述べるのも正しい (しかし役に立たない) ことに注意することも重要です。分析時の多くのアルゴリズムは Big Oh を使用して記述されていますが、Big Theta を使用して範囲を狭める方が適切です。つまり、特定のアルゴリズムに関して最も低く、最も正確な次数を意味します。

注意して、正式な定義を読んでください!

于 2013-08-16T09:30:58.543 に答える
2

実行時間が長くなると、アルゴリズムの効率が低下しますか?

必要はありません。プログラムの効率は、かかる時間だけでなく、使用しているリソースによっても測定されます。スペースは、効率を考慮する際に考慮すべきもう 1 つの要素です。

ウィキより:-

最大限の効率を得るために、リソースの使用を最小限に抑えたいと考えています。ただし、さまざまなリソース (時間、空間など) を直接比較することはできないため、2 つのアルゴリズムのどちらがより効率的であると見なされるかは、多くの場合、効率のどちらの尺度が最も重要であると見なされているかによって異なります。 、またはメモリ使用量を最小限に抑えるため、またはその他の手段のために？

于 2013-08-16T09:38:46.883 に答える
1

一般的に: はい。ただし、サブ 1 秒の範囲でダウンしている場合は、混乱を招く可能性のある多くのノイズがあります...

各テストを何度も実行し、結果にいくつかの統計を使用します (たとえば、どれだけ気にするかに応じて、平均または平均/偏差)

および/またはより多くの素数を見つけるなど、より多くの作業を行う

于 2013-08-16T09:30:02.050 に答える
1

要するに、はい、効率が時​​間効率を意味するのであれば。メモリに関する考慮事項もあります。

ただし、測定方法には注意してください。タイミング ツールが正確であることを確認してください。

他に何も実行していないときに、必ず同じマシンで測定してください。
適切な比較のために、必ず数回測定し、平均値と分散を取得してください。
誰かにあなたのコードをレビューしてもらい、あなたが思っていることを実行していることを確認してもらうことを検討してください。

于 2013-08-16T09:30:31.127 に答える
1

通常、アルゴリズムの効率は、大量の入力をどれだけ効率的に処理できるかによって測定されます。10,000 の数値はそれほど大きな入力ではないため、エラトステネスのふるいが速くなり始める前に、より大きな数値を使用する必要がある場合があります。

または、実装の1つに大きな問題がある可能性があります

最後に、アルゴリズムの効率は、必要なメモリの量によって測定できます (ただし、この測定法はあまり一般的ではありません。特に最近ではメモリが非常に安価になっているためです)。

于 2013-08-16T09:35:44.543 に答える