結果分析のO記法と一意性が分析される際に、驚くべき(厳しい、奇妙な)Big O分析のアルゴリズム
答えて
多項式の非決定論的な複雑さは、特に多項式と同じになる可能性がある(確かに考えられるとは考えられない)可能性をもって、私の投票を得ます。同じように、量子コンピューティングから理論的に利益を得ることができるもの(N.B.はこのすべてが決してすべてのアルゴリズムではない)です。
私の投票権を得る他のものは、任意の精度の数値に対する一般的な数学演算です - これは、大きな数値を乗算するなどのことは小さなものを乗算するよりも高価です。クヌス(これは誰にも知られてはいけない)の中でこれについてかなりの分析があります。 Karatsubaの方法は、2つの要素を数字(A1; A2)(B1; B2)で半分に切り、A1 B1、A1 B2、A2 B1、A2 B2を別々に掛けて、結果を結合します。希望の場合は繰り返し...
Karatsubaの方法は素晴らしいですが、これは本当です。しかし、高速フーリエ変換はコンボリューションを実行するので、既知の最速の乗算を実行するために使用することができます。数字が混合入力サイズのFFTを書き込んで調整することを妥当とするのに十分な大きさであると仮定します。 –
ええと、私はそれを見なければならないでしょう。正確な整数の乗算を保証するためにコンポーネントがどれくらい正確に必要ですか? – Edmund
私が理解しているように、最終数値を保持するのに十分な精度が必要です。 FFT乗算手法は整数型で直接使用することもできますが、常に正確な答えが得られます。私はここにクヌスのコピーを持っていませんが、私は彼がそのテクニックについて言及し、それを乗り越えると思います。 –
これはちょっとシンプルですが、櫛形は私の心を少し吹き飛ばします。
http://en.wikipedia.org/wiki/Comb_sort
それが過度に複雑バブルソートのように読み、それはO(N *ログ[N])で、ほとんどの部分は、このような単純なアルゴリズムです。私はそれがやや印象的であることがわかります。
高速フーリエ変換のためのアルゴリズムは非常に多く、その有効性が三重であることを証明する数学は数独であることを証明するのは楽しいものでした。
http://en.wikipedia.org/wiki/Fast_Fourier_transform
私はかなり容易プライム基数、複数のプライム基数、および混合基数アルゴリズムが、その大きさプライムかなりクールですセットで動作するものを理解することができます。
私が持っている(かなりの)いくつかの例:
- (償却)逆アッカーマン時間の操作をサポートしunion-findデータ構造。データ構造がコード化するのが非常に簡単なので、特にうれしいことです。
- Splay trees で実行されるスプレイツリーは、自己釣り合いのバイナリツリーです(つまり、BST以外の情報は保存されません)。Amortized analysisは本質的にスプレイツリーの境界を証明するために作成されました。
- これは、償却された一定時間の優先順位キュー操作の大部分を実行するので、Dijkstra's algorithmのランタイムとその他の問題が改善されます。スプレイツリーと同様に、次のようなエラーが発生します。
- 線形時間逆Ackで最小全域木を計算するBernard Chazelleのアルゴリズムermann時間。このアルゴリズムでは、従来のpriority queueの亜種であるsoft heapsが使用されていますが、一部の「破損」が発生し、クエリが正しく応答されないことがあります。
- MSTのトピックについて:最適なアルゴリズムはgiven by Pettie and Ramachandranでしたが、実行時間はわかりません!
- ランダム化されたアルゴリズムがたくさんあります。私は一例を挙げておきます:Delaunay三角測量は、期待されるO(n log n)時間でincrementally adding pointsで計算できます。私はそれを見ていないが、分析は明らかに複雑である。
- "ビットトリック"を使用するアルゴリズムはきちんとすることができます。 sorting in O(n log log n)時間(そして線形空間) - それは、単なる比較以上のものを使ってO(n log n)の障壁を破ります。
- Cache-oblivious algorithmsには、しばしば興味深い分析があります。たとえば、cache-oblivious priority queues(3ページを参照)は、サイズn、n 2/3、n 4/9などのログログレベルを使用します。
- (静的)範囲 - 配列の最小クエリはきれいです。 standard proofは、削減に関する制限をテストします。範囲最小クエリは、ツリー内の最小共通祖先に縮小され、特定の種類の配列の範囲最小クエリに縮小されます。配列。最後のステップでもかわいいトリックを使用します。
2次配列検索は非常に興味深いものです。各行が左右にソートされ、各列がトップダウンでソートされたN×Nの2次元数値配列が得られます。タスクは、配列内の特定の番号を見つけることです。
再帰アルゴリズム:中間の要素を選択し、ターゲット番号と比較し、配列の四分の一を捨てる(比較の結果に応じて)、残っている3つの四半期に再帰的に適用することは非常に興味深い。
シェルソート。様々な増分を伴う多数の変種がありますが、そのほとんどは恩恵を受けません。complexity analysis simpler。
- 1. Big-O表記:暗号化アルゴリズム
- 2. この指数アルゴリズムのBig-O複雑さの単純化
- 3. アルゴリズムのBig O/Timeの複雑さを見つける方法
- 4. このアルゴリズムのbig-O表記法とは何ですか?
- 5. Pythonデータ構造のbig-O解析のリスト
- 6. Big-O表記の定義
- 7. Big Oの例2^n
- 8. 関数内の関数を使ったBig-O解析
- 9. big-oを使用した時間複雑度解析
- 10. Big O - ネストされたループ
- 11. C++ステートメントのBig-O 'delete [] Q;' O(1)またはO(n)?
- 12. アルゴリズムの再帰の分析
- 13. 変動分析のアルゴリズム
- 14. 特定のdouble forループのBig O
- 15. 漸近分析では、 - O(f(n)+ g(n))= O(max {f(n)、g(n)})
- 16. ネストループ内の乗算数:Big O
- 17. 単純なBig-Oの計算
- 18. Big Oの定数部分を理解することの問題
- 19. リンクリストのアルゴリズム複雑さの分析
- 20. ソーシャルネットワーク分析(SNA)アルゴリズムの依頼
- 21. アルゴリズムの分析/パフォーマンスについて
- 22. 単語のテキストを分析するアルゴリズム
- 23. O(fib n)複雑アルゴリズム?
- 24. 1つのリンクされたリスト上での操作のBig-O
- 25. このコードの上限であるBig Oとは
- 26. フィボナッチのさまざまな実装のBig-O
- 27. forループの入れ子になった一連のBig O
- 28. Pythonの `len()`関数のbig-o表記法は何ですか?
- 29. Big-O表記でのデータ構造のパフォーマンス
- 30. linq .whereのBig Oとは何ですか?
それはアルゴリズムですか? – shoosh
@pこの回答はおそらく、リンク専用だとしても問題ありません。 「Ackermannの機能」はインターネット上でそれを見つけるのに十分であり、おそらく話題にならない質問は説明ではなくアルゴリズムを求めるだけである。 – royhowie