1

今、私はアルゴリズムの紹介、クイックソートの章を読んでいました。末尾再帰を最適化に使用できるとのことでした。

QUICKSORT'(A, p, r)
    while p < r
     do ▸ Partition and sort left subarray.
    q ← PARTITION(A, p, r)
    QUICKSORT'(A, p, q - 1)
    p ← q + 1

ただし、上記のコードのスタックの深さは、反復ごとにピボット番号が [1,n-1] [n] の場合、O(n) になります。

QUICKSORT (A, p, r )
    while p < r
        do Partition and sort the small subarray Þrst
        q ← PARTITION(A, p, r )
        if q − p < r − q
            then QUICKSORT (A, p, q − 1)
                    p ← q + 1
        else QUICKSORT (A, q + 1, r )
                    r ← q − 1

上記のコードで私が理解しているのは、最初に長さが短い部分配列を処理するということです。しかし、なぜ O(lgn) に還元できるのでしょうか? ピボットがまだ [1,n-1] [n] である場合、O(n) スタックの深さを維持していると思います。

4

1 に答える 1

0

二分木を考えてみてください。任意の二分木。

ここで、各ノードで、葉に到達するまで、より少ないノードでサブツリーをトラバースすることを選択します。

あなたがたどった道の長さはどれくらいですか？O(log n)? はい？

ここも同じです。

于 2014-03-18T04:09:27.637 に答える