7

結果のO表記と分析方法の独自性の両方に関して、驚くべき（タフで奇妙な）複雑さ分析を持っていると思うアルゴリズムはどれですか？

4

6 に答える 6

16

私は（かなり）いくつかの例を持っています：

  • (償却された) 逆アッカーマン時間での操作をサポートする、union-find データ構造。データ構造は非常に簡単にコーディングできるため、特に優れています。
  • スプレー ツリー。これは、自己均衡バイナリ ツリーです (つまり、BST 以外に余分な情報は保存されません。つまり、赤/黒の情報はありません。 償却分析は、本質的に、スプレー ツリーの境界を証明するために考案されました。スプレー ツリーは、償却された対数時間で実行されます。 、しかし最悪の場合の線形時間です。
  • Fibonacci heapsは、償却された定数時間でほとんどの優先キュー操作を実行するため、Dijkstra のアルゴリズムの実行時間やその他の問題が改善されます。スプレー木と同様に、洗練された「ポテンシャル関数」の証明があります。
  • 線形時間逆アッカーマン時間で最小スパニング ツリーを計算するための Bernard Chazelle のアルゴリズム。このアルゴリズムでは、従来の優先キューの変形であるソフト ヒープを使用しますが、 「破損」が発生し、クエリが正しく応答されない場合があります。
  • MST のトピックについて: Pettieと Ramachandran によって最適なアルゴリズムが提供されましたが、実行時間はわかりません!
  • 多くのランダム化されたアルゴリズムには、興味深い分析があります。例を 1 つだけ挙げます。ドローネ三角形分割は、ポイントを段階的に追加することで、予想される O(n log n) 時間で計算できます。私は見ていませんが、分析は明らかに複雑です。
  • たとえば、O(n log log n) 時間 (および線形空間) での並べ替えなど、「ビット トリック」を使用するアルゴリズムは巧妙です。そうです。単純な比較以上のものを使用して、O(n log n) の壁を打ち破ります。
  • キャッシュを無視するアルゴリズムには、多くの場合、興味深い分析があります。たとえば、キャッシュ無視優先度キュー(3 ページを参照) は、サイズ n、n 2/3、n 4/9などのログ ログ n レベルを使用します。
  • 配列に対する (静的) 範囲最小クエリは適切です。標準的な証明は、削減に関する制限をテストします。範囲最小クエリは、ツリー内の最小共通祖先に削減され、特定の種類の配列内の範囲最小クエリに削減されます。最後のステップもかわいいトリックを使っています。
于 2009-02-23T08:14:46.020 に答える
2

2D 順序付き検索分析は非常に興味深いものです。各行が左右に並べ替えられ、各列が上から下に並べ替えられた NxN の数値の 2 次元数値配列があります。タスクは、配列内の特定の数値を見つけることです。

再帰的アルゴリズム: 中央の要素を選択し、ターゲット数と比較し、(比較の結果に応じて) 配列の 4 分の 1 を破棄し、残りの 3 分の 1 に再帰的に適用するという分析は非常に興味深いものです。

于 2009-02-24T08:46:51.693 に答える
2

アッカーマン関数.

于 2009-02-23T07:43:32.867 に答える
2

これはちょっと単純ですが、Comb Sort は私の心を少し吹き飛ばします。

http://en.wikipedia.org/wiki/Comb_sort

これは、非常に複雑なバブル ソートのように読める大部分の単純なアルゴリズムですが、O(n*Log[n]) です。私はそれがやや印象的だと思います。

高速フーリエ変換の膨大なアルゴリズムも印象的です。それらの有効性を証明する数学はトリッピーで、自分でいくつかを証明しようとするのは楽しかったです。

http://en.wikipedia.org/wiki/Fast_Fourier_transform

素数、複数の素数、および混合基数のアルゴリズムをかなり簡単に理解できますが、サイズが素数であるセットで機能するものは非常にクールです。

于 2009-02-23T07:50:28.903 に答える
1

非決定論的な多項式の複雑さは、特に多項式と同じであることが判明する可能性がある (確かにありそうにないと考えられている) 場合に、私の票を獲得します。同じように、量子コンピューティングから理論的に恩恵を受けることができるものはすべて (注意: このセットは決してすべてのアルゴリズムではありません)。

私の投票を得るもう1つは、任意精度の数値に対する一般的な数学演算です。これは、大きな数を掛けると小さな数を掛けるよりもコストがかかるなどのことを考慮する必要がある場合です。これについては、Knuth でかなり多くの分析が行われています (これは誰にとってもニュースではないはずです)。カラツバの方法は非常に巧妙です: 2 つの因数を桁 (A1;A2)(B1;B2) で半分に切り、A1 B1、A1 B2、A2 B1、A2 B2 を別々に掛けてから、結果を結合します。必要に応じて再帰...

于 2009-02-23T07:48:27.660 に答える