2

セグメント ツリーの複雑さを理解するのに問題があります。1 つのノードのみを変更する必要がある update 関数がある場合、その複雑さは log(n) になることは明らかです。しかし、（a、b）がチェックする必要がある間隔であるクエリ（a、b）の複雑さがlog（n）である理由がわかりません。これを理解するための直感的/正式な証拠を誰かに提供してもらえますか?

4

3 に答える 3

3

間隔 (x,y) をクエリする場合は 4 つのケースがあります。

FIND(R,x,y) //R is the node
% Case 1
    if R.first = x and R.last = y   
        return {R}
% Case 2
    if y <= R.middle
        return FIND(R.leftChild, x, y) 
% Case 3
    if x >= R.middle + 1 
        return FIND(R.rightChild, x, y) 
% Case 4
    P = FIND(R.leftChild, x, R.middle)
    Q = FIND(R.rightChild, R.middle + 1, y)    
    return P union Q.

直観的に、最初の 3 つのケースでは、ツリーの高さのレベルが 1 減少します。ツリーの高さは log n であるため、最初の 3 つのケースのみが発生した場合、実行時間は O(log n) になります。

最後のケースでは、FIND() は問題を 2 つのサブ問題に分割します。ただし、これは多くても 1 回しか発生しないと断言します。FIND(R.leftChild, x, R.middle) を呼び出した後、間隔 [x, R.middle] について R.leftChild を照会しています。R.middle は R.leftChild.last と同じです。x > R.leftChild.middle の場合、ケース 1 です。x <= R.leftChild の場合、呼び出します

FIND ( R.leftChild.leftChild, x, R.leftChild.middle );
FIND ( R.leftChild.rightChild, R.leftChild.middle + 1, , R.leftChild.last );

ただし、2 番目の FIND() は R.leftChild.rightChild.sum を返すため一定の時間がかかり、問題は 2 つの部分問題に分離されません (厳密に言えば、問題は分離されますが、1 つの部分問題は O(1) 時間かかります)。解決する）。

同じ分析が R の rightChild にも当てはまるため、case4 が最初に発生した後、実行時間 T(h) (h はツリーの残りのレベル) は次のようになると結論付けます。

T(h) <= T(h-1) + c (c is a constant)
T(1) = c

これにより、次の結果が得られます。

T(h) <= c * h = O(h) = O(log n) (since h is the height of the tree)

ということで証明を終わります。

貢献するのはこれが初めてです。問題がある場合は、親切に指摘してください。回答を編集します。

于 2015-06-28T05:42:28.627 に答える