アルゴリズムの有効性を分析する際に、空間と時間以外のパラメーターについて知りたいと思いました。たとえば、暗号化アルゴリズムを開発する際に、効果的なトラップ機能に焦点を当てることができます。他にどのようなことを考えることができますか？
13 に答える
8
何よりもまず、正しさがあります。入力に関係なく、アルゴリズムが常に機能することを確認してください。アルゴリズムが処理するように設計されていない入力の場合でも、アプリケーション全体をクラッシュさせるのではなく、エラーメッセージを出力する必要があります。欲張りアルゴリズムを使用する場合は、手作業で試したいくつかのケースだけでなく、すべてのケースでそれらが本当に機能することを確認してください。
次に、実用的な効率があります。O（N 2）アルゴリズムは、実際にはO（N）アルゴリズムよりもはるかに高速です。実際のテストを行い、理論的な結果にあまり依存しないでください。
次に、実装の容易さがあります。通常、100個の整数の配列を1回ソートするのに最適なイントロソートの実装は必要ないので、気にしないでください。
アルゴリズムの最悪のケースを探し、可能であれば、それらを回避するようにしてください。一般的に高速なアルゴリズムを使用しているが、最悪のケースが非常に悪い場合は、その最悪のケースを検出し、一般的に低速であるがその単一のケースに適した別のアルゴリズムを使用して解決することを検討してください。
空間と時間のトレードオフを考慮してください。より良い速度を得るためにメモリを買う余裕があれば、特に本当に速度が必要な場合は、おそらくそれをしない理由はありません。あなたがメモリを買う余裕がないが、遅くする余裕があるなら、それをしてください。
可能であれば、既存のライブラリを使用してください。たとえば、GMPを使用できる場合は、独自の多倍長ライブラリをロールしないでください。C ++の場合、ブーストやSTLコンテナーやアルゴリズムのようなものでさえ、何年にもわたって多くの人々によって開発されており、おそらくあなたが一人でできるよりも優れています。
于 2010-03-08T14:56:22.217 に答える
6
安定性（ソート） -アルゴリズムは等しい要素の相対的な順序を維持しますか？
数値安定性-非常に大きいまたは小さい実数が使用されている場合、アルゴリズムはエラーを起こしやすいですか？
正しさ-アルゴリズムは常に正しい答えを出しますか？そうでない場合、許容誤差はどのくらいですか？
一般性-アルゴリズムは多くの状況で機能しますか（たとえば、多くの異なるデータ型で）？
コンパクトさ-アルゴリズムのプログラムは簡潔ですか？
並列化可能性-実行の同時スレッドの数が増えると、パフォーマンスはどの程度向上しますか？
キャッシュの認識-アルゴリズムは、コンピューターのキャッシュを最大限に活用するように設計されていますか？
キャッシュの忘却-アルゴリズムは特にキャッシュサイズ/キャッシュラインサイズに合わせて調整されていますか、それともキャッシュのパラメーターに関係なくうまく機能しますか？
于 2010-03-08T16:36:42.313 に答える
5
安定性-一部のアルゴリズムは、特定のテスト条件で「爆発」する可能性があります。たとえば、実行に非常に長い時間がかかるか、非常に大量のメモリを使用するか、場合によっては終了しません。
于 2010-03-08T14:50:53.540 に答える
5
複雑。2つのアルゴリズムは他のすべての点で同じであり、はるかに単純なものが、将来のカスタマイズと使用のためのはるかに優れた候補になります。
並列化のしやすさ。ユースケースによっては、違いがない場合や、10000コアを使用できないため、アルゴリズムが役に立たない場合があります。
于 2010-03-08T14:53:15.933 に答える
4
浮動小数点演算を実行するアルゴリズムの場合、丸め誤差の累積が考慮されることがよくあります。
于 2010-03-08T15:07:48.920 に答える
4
組み込みアルゴリズムの消費電力（スマートカードを考えてください）。
于 2010-03-08T15:14:11.750 に答える
3
アルゴリズムの分析で頻繁に測定される重要なパラメーターの1つは、キャッシュヒットとキャッシュミスのパラメーターです。これは非常に実装とアーキテクチャに依存する問題ですが、ある程度一般化することは可能です。アルゴリズムの特に興味深い特性の1つは、キャッシュを無視することです。これは、アルゴリズムが、変更なしで、異なるキャッシュサイズと構造を持つ複数のマシンでキャッシュを最適に使用することを意味します。
于 2010-03-08T14:54:38.133 に答える
3
時間と空間は大きなものであり、それらは非常に明白で決定的なように見えるので、それらはしばしば資格を与えられるべきです（1）。OPが「基準」や「プロパティ」ではなく「パラメータ」という単語を使用しているという事実は、これをいくらか示しています（時間と空間の大きなO値が、基礎となるアルゴリズムを構成するのに十分であるかのように）。
その他の基準は次のとおりです。
- 適用範囲
- 複雑
- 数学的扱いやすさ
- 結果の決定性
- チューニングのしやすさ（前述の「複雑さ」と「触覚性」に関係している可能性があります）
- アルゴリズムを並行して実行する機能
（1）「修飾」：他の回答で示唆されているように、-technically- O（n ^ 2）アルゴリズムは、90％のケースでO（n）アルゴリズムよりも高速であることがわかります（ところで、実際のケースの100％であることが判明する可能性があります）
于 2010-03-08T14:55:29.410 に答える
2
最悪の場合と最良の場合も、特に入力のいくつかの条件にリンクされている場合に興味深いものです。入力データにいくつかのプロパティが表示されている場合、このプロパティを利用するアルゴリズムは、同じタスクを実行するがそのプロパティを使用しない別のアルゴリズムよりもパフォーマンスが向上する可能性があります。
たとえば、多くの並べ替えアルゴリズムは、入力が特定の方法で部分的に順序付けられている場合に非常に効率的に実行され、アルゴリズムが実行する必要のある操作の数を最小限に抑えます。（入力がほとんどソートされている場合、挿入ソートはうまく適合しますが、それ以外の場合はそのアルゴリズムを使用することはありません）
于 2010-03-08T14:52:59.927 に答える
2
アルゴリズム全般について話している場合、（現実の世界では）CPU /ファイルシステム（読み取り/書き込み操作）/帯域幅の使用法について考える必要があるかもしれません。
確かに、これらは最近心配する必要のあるもののリストのはるか下にありますが、十分な量のデータと十分に安価なインフラストラクチャを考えると、どちらか一方を楽にするためにコードを微調整する必要があるかもしれません。
于 2010-03-08T15:12:14.917 に答える
1
興味があるのはパラメータではなく、アルゴリズムの固有のプロパティです。
とにかく、あなたが興味を持ち、アルゴリズムを分析する可能性のある別のプロパティは、ヒューリスティック（またはむしろ近似アルゴリズム）、つまり正確な解を見つけられないアルゴリズムに関係しますが、（うまくいけば）十分に良いものです。
最悪の場合、解が理論上の最適解からどれだけ離れているかを分析できます。たとえば、既存のアルゴリズム（どれを忘れたか）は、最適な巡回セールスマンツアーを2倍に近似します。つまり、最悪の場合、最適なツアーの2倍の長さになります。
別のメトリックは、ランダム化が望ましくない最悪の場合の動作を防ぐために使用されるランダム化アルゴリズムに関するものです。一例はランダム化されたクイックソートです。クイックソートの実行時間は最悪の場合O（n 2）であり、これは避けたいものです。事前に配列をシャッフルすることで、非常に高い確率で最悪の場合（つまり、すでにソートされた配列）を回避できます。この確率がどれだけ高いかを知ることは重要です。これは、確率論を使用して分析できるアルゴリズムのもう1つの固有のプロパティです。
于 2010-03-08T14:54:37.277 に答える
1
数値アルゴリズムの場合、連続性の特性もあります。つまり、入力をわずかに変更しても、出力もわずかに変更されるかどうかです。ディスカッションと学術論文へのリンクについては、LambdaTheUltimateのプログラムの継続性分析も参照してください。
怠惰な言語の場合、厳密性もあります：厳密fと呼ばれる場合f _|_ = _|_（ここで、は（ドメイン理論の意味で）下部_|_を示し、非終了、エラーなどのために結果を生成できない計算）、それ以外の場合は非-厳しい。たとえば、関数は非厳密です。これは、が厳密であるためです。\x -> 5(\x -> 5) _|_ = 5\x -> x + 1
もう1つのプロパティは、決定性です。アルゴリズムの結果（または実行時間やスペース消費などの他のプロパティ）が入力のみに依存するかどうかです。
于 2010-03-08T17:12:03.643 に答える
0
さまざまなアルゴリズムの品質に関する他の回答のこれらすべてのことは重要であり、考慮する必要があります。
ただし、時間とスペースは、入力のサイズ（n）と比較してある程度変化する2つのものです。では、nに応じて他に何が変わる可能性がありますか？
I/Oに関連するものがいくつかあります。たとえば、ディスクへの書き込み回数は重要ですが、スペースと時間の見積もりだけでは直接表示されない場合があります。これは、同じメモリ位置への書き込み数が一部のアルゴリズムで重要なメトリックであるフラッシュメモリで特に重要になります。
もう1つのI/Oメトリックは、「おしゃべり」です。ネットワークプロトコルは、より短いメッセージをより頻繁に送信し、別のネットワークプロトコルと同じスペースと時間になる可能性がありますが、システムの一部の側面（おそらく課金？）により、メッセージのサイズまたは数を最小限に抑えることが望ましい場合があります。
そして、それは私たちにコストをもたらします。これは、時には非常に重要なアルゴリズムの考慮事項です。アルゴリズムのコストは、スペースと時間の両方によってさまざまな量で影響を受ける可能性があります（サーバーのストレージスペースとデータ転送のギガビットの個別のコストを考慮してください）が、コストは全体として最小化する必要があるため、独自のbig-O推定。
于 2010-03-08T17:57:32.703 に答える