-6

ソートされていない方法で与えられた数値を X:{4,2,5,1,8,2,7} と言う

数のランクをどのように見つけますか??

例: 4:4 のランク : 5:5 のランク

複雑さは O(lg n) でなければなりません。

Red Black Trees と Augmented Data structure アプローチ (最近の魅力的なものの 1 つ) の助けを借りて、O(lg n) の複雑さで実行できます。注文統計ツリーを利用しようOrder Statistic Tree

Algorithm:
RANK(T,x)

//T: order-statistic tree, x: node(to find rank of this node)
r = x.left.size + 1
y=x
While y != T.root
    if y==y.p.right
        r= + y.p.left.size + 1
    y=y.p
Return r;

どんな助けでも大歓迎です。

これよりも良いアプローチはありますか??

4

1 に答える 1

2

ソートされていない方法で数値が与えられた場合、たとえばX:{4,2,5,1,8,2,7}

数のランクをどのように見つけますか.

ランクは、要素がソートされたときの位置です。

複雑さは O(lg n) でなければなりません。

それ無理。各要素を少なくとも 1 回は確認する必要があります。したがって、 を超えることはできずO(n)、O(n) では自明です。

  • foundに設定false
  • smaller0に設定
  • の各数値に対してarray
    • 数がより小さい場合needle
      • 小さいカウンターをインクリメントする
    • 数がneedle
      • foundに設定true
  • if found、 return smaller+1、そうでなければエラーを返す

Red Black Trees と Augmented Data 構造アプローチ (最近の魅力的なものの 1 つ) の助けを借りて、O(lg n) の複雑さで実行できます。注文統計ツリーを活用しよう

問題は、順序統計ツリーがなく、作成する時間がないことです。順序統計ツリーの構築には、時間以上のO(lg n)時間がかかります*。

しかし、順序統計ツリーを構築する時間があるとしましょう。二分探索ツリーでソートされたノードのリストを抽出するには線形時間がかかるため、順序統計ツリーを構築することは、配列を直接ソートするよりも高速ではありません。

それでは、配列を直接ソートしましょう。次に、要素のランクを見つけることは、並べ替えられた配列で要素を見つけることと同じです。これはよく知られたタスクで、O(lg n)二分探索 (要素が見つかるまで配列を半分に分割することを繰り返します) で解決できます。順序統計ツリーはまったく役に立たないことがわかりました。実際、二分探索は順序統計ツリーのルックアップと考えることができます (ただし、ツリーは実際には存在しません)。

実行時に変更できる場合xは、順序統計ツリーが役に立ちます。次に、要素の削除/追加にはTh(lg n)(最悪の場合) 時間がかかりTh(n)ますが、要素を移動する必要があるため、通常の並べ替えられた配列では * (平均的な場合) かかります。不変の順序統計ツリーでは、単純な配列よりxも高速化されません。

* 技術的にO(lg n)は、漸近的に大きくなる関数のセットですlg n。「以上」と言うときO(lg n)、正しい解釈は「 のすべての関数よりも多い」O(lg n)です。ちなみに、これは実行時間がomega(lg n)(オメガは小文字であることに注意してください) と言っているのと同じです。

Th(lg n)lg n定数まで漸近的に等しい関数のセットです。技術的に正しいままで O(lg n) と英語を使用して同じことを表現するのは厄介です。

于 2013-03-04T10:56:16.710 に答える