すべての Big-O 表記のマスター リストはありますか? データ構造、アルゴリズム、それぞれに対して実行される操作、平均的なケース、最悪のケースなど。
4602 次
6 に答える
8
Dictionary of Algorithms and Data Structuresはかなり包括的なリストであり、アルゴリズムの説明に複雑さ (Big-O) が含まれています。さらに情報が必要な場合は、リンクされた参考文献の 1 つに記載されており、フォールバックとして常にウィキペディアがあります。
于 2008-10-07T21:49:41.287 に答える
6
コーメンの本は、Big-O のパフォーマンスに対するアルゴリズムの丸暗記ではなく、与えられたアルゴリズムに対して Big-O が何であるかを証明する方法を教えることを目的としています。前者は後者よりもはるかに価値があり、投資が必要です。
于 2008-10-07T21:31:49.093 に答える
2
C++ では、STL 標準はアルゴリズムの Big-O 特性とスペース要件によって定義されます。そうすれば、競合する STL の実装を切り替えても、プログラムが同じようなランタイム特性を持っていることを知ることができます。特に優れた STL 実装は、特定のタイプの特別なケースのリストでさえ、標準要件よりも優れている可能性があります。
スペース消費と速度を簡単に比較検討できるため、特定の問題に対して適切なイテレータまたはリスト タイプを簡単に選択できるようになりました。
もちろん、すべての定数が削除されているため、Big-O はガイドラインにすぎません。アルゴリズムが k*O(n) で実行される場合、O(n) として分類されますが、k が十分に大きい場合、n と m の値によっては O(n^2) よりも悪い可能性があります。
于 2008-10-07T21:47:31.197 に答える
2
Cormen、Leisersen、Rivest による「 Introduction to Algorithms 」を試してください。そこにない場合、おそらく知る価値はありません。
于 2008-10-07T21:29:55.023 に答える
0
Introduction to Algorithms, Second Edition、別名 CLRS (Cormen、Leiserson、Rivest、Stein) は、私が考えることができる最も近いものです。
それが失敗した場合は、Knuth によるThe Art of Computer Programming を試してください。それらにない場合は、おそらく実際の調査を行う必要があります。
于 2008-10-07T21:30:41.433 に答える