与えられた2-3 tree Tとその木のあるノードvを指すポインタがあると、アルゴリズムはノードの鍵を変えることができるので、 3ツリー、O(logn/loglogn)償却効率?2-3 BST木のアルゴリズムを見つける
1
A
答えて
2
番号
アルゴリズムfを使用して、O(n*logn/loglogn)
時間の複雑さで配列を並べ替えることができると仮定します。
sort array A of length n:
(1) Create an 2-3 tree of size n, with no importance to keys. let it be T.
(2) store all pointers to nodes in T in a second array B.
(3) for each i from 0 to n:
(3.1) f(B[i],A[i]) //modify the tree: pointer: B[i] new value: A[i]
(4) extract elements from T back to A inorder.
正確: f
の各活性化後木が合法です。 T
およびすべての要素がA
のすべての要素に対してf
を有効にした後、ツリーは合法であり、すべての要素を含みます。したがって、Aから要素を抽出すると、ソートされた配列が返されます。
複雑:
(1)ツリーを作成する[我々は入れキーなし重要性は] O(n)
である私たちは、すべての要素に0
を置くことができ、それは
問題ではない(2)T
を反復してB
さを作成しますO(n)
(3)このようにしてそれをn
回呼び出し、f
O(logn/loglogn)
され活性化されO(n*logn/loglogn)
(4)要素を抽出するだけトラバースある:従ってO(n)
。総複雑度はO(n*logn/loglogn)
ですが、ソートは比較ベースのアルゴリズムではOmega(nlogn)
の問題です。矛盾。
結論:希望f
は存在しません。
関連する問題
- 1. アルゴリズムが無向木のパスを見つける
- 2. BSTの高さを非再帰的に見つけるか?
- 3. 重複を見つけるアルゴリズム
- 4. 無向グラフパスを見つけるアルゴリズム
- 5. 共起行列を見つけるアルゴリズム
- 6. JPA/JPQL:単方向木のルート要素を見つける
- 7. "良い"隣人 - グラフの色付けを見つけるアルゴリズム?
- 8. アルゴリズム:不完全な値を持つモードを見つける
- 9. 木の分割征服アルゴリズム
- 10. グラフのノードを訪問する順序を見つけるアルゴリズム
- 11. De-Boorsアルゴリズムを実装してBスプラインの点を見つけるアルゴリズム
- 12. アルゴリズムのBig O/Timeの複雑さを見つける方法
- 13. 前の日曜日の日付アルゴリズムを見つける
- 14. 最短経路を見つけるためのダイクストラのアルゴリズム?
- 15. アルゴリズムは、行列の行列を見つけるために
- 16. 可能なすべての位置を見つけるアルゴリズム
- 17. セットカバー問題の最小サイズセットカバーを見つけるアルゴリズム
- 18. 円周上のピクセル座標を見つけるアルゴリズム
- 19. スライディングウィンドウで文字列の一致を見つけるアルゴリズム
- 20. 交差ボックスから実線のポリゴンを見つけるアルゴリズム?
- 21. 次の多項式を見つけるアルゴリズム
- 22. 配列内の最小要素を見つける再帰アルゴリズム
- 23. Aprioriアルゴリズムの最小サポートを見つける方法
- 24. 近くの点を見つけるアルゴリズムですか?
- 25. GPS座標のデータベースで「ホットスポット」を見つけるアルゴリズム
- 26. パターンに一致する最短文を見つけるアルゴリズム
- 27. 関連する単語をテキスト内で見つけるアルゴリズム
- 28. 入力ポイントを使って数字を見つけるアルゴリズム
- 29. Dijkstraアルゴリズムを使って最短ルートを見つける
- 30. PHPでアルゴリズムを見つけることができません
同じ理由でOmega(n log n)ソーティングバリアを破ることができるため、Omega(log n)よりも速くアップデートすることはできません。 – templatetypedef