5

私はアルゴリズムのクラスのために勉強しているだけで、QuickSort を調べています。アルゴリズムとその仕組みは理解していますが、1 日の終わりに比較の回数を取得する方法や、logn が実際に何を意味するのかはわかりません。

私は以下の範囲で基本を理解しています:

x=logb(Y) then
b^x = Y

しかし、これはアルゴリズムのパフォーマンスに関して何を意味するのでしょうか? それはあなたがしなければならない比較の数です、私はそれを理解しています...しかし、全体のアイデアはとても理解できないようです. 同様に、QuickSort の場合、各レベル K の呼び出しには、それぞれ2^kが長さのサブリストを含む呼び出しが含まれます。n/2^K.

したがって、比較の数を見つけるために合計します。

log n
Σ 2^k. 2(n/2^k) = 2n(1+logn)
k=0

log n まで合計するのはなぜですか? 2n(1+logn) はどこから来たのですか? 私の説明があいまいで申し訳ありません、私はとても混乱しています。

4

5 に答える 5

4

完全でバランスの取れた二分木を考えると、レイヤーごとに1 + 2 + 4 + 8+...の頂点があります。ツリー内の頂点の総数が2^n-1の場合、1 + 2 + 4 + 8 + ... + 2 ^（n-1）の頂点があり、レイヤーごとにカウントされます。ここで、N = 2 ^ n（木のサイズ）とすると、木の高さはn、n = log2（N）（木の高さ）になります。これが、これらのBig O式でlog（n）が意味することです。

于 2011-05-01T10:12:57.157 に答える
1

以下はサンプルツリーです。

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

ツリーのノード数は 7 ですが、ツリーの高さは log 7 = 3 です。log は、分割統治法がある場合に発生します。クイック ソートでは、リストを 2 つのサブリストに分割し、豊富な小さなリストになるまでこれを続けます。分割にはlogn時間がかかります (平均的なケース)、分割の高さは であるため、log n各レベルの分割には O(n) かかります。これは、平均の各レベルで N 個の数を分割するためです (分割するにはリストが多すぎる可能性がありますが、数字の平均数は N です)。各レベルで、実際にはリストの数のいくつかは N です)。したがって、単純な観察のために、バランスの取れたパーティション ツリーがある場合はlog n、パーティショニングの時間があります。つまり、ツリーの高さを意味します。

于 2011-05-01T10:07:59.190 に答える
1

1 秒間 b ツリーのことを忘れる

here' math : log2 N = k は同じ 2^k=N .. log の定義です。自然対数 (e) N = k 別名 e^k = n、または 10 進 log10 N = k は 10 です。 ^k = n

2 完璧でバランスの取れた木を見る

1
1+ 1 1 + 1 + 1+ 1 8 1 16 1 など

要素はいくつ？1+2+4+8..etc 、したがって、2 レベルの b-tree には 2^2-1 要素があり、3 レベルのツリーには 2^3-1 などがあります。SO HERE'S MAGIC FORMULA: N_TREE_ELEMENTS= number of levels ^ 2 -1 、または log の定義を使用: log2 number OF levels= number_of_tree_elements ( -1 については忘れてもかまいません)

3、N 要素の B ツリーで、K レベル (別名高さ) で要素を検索するタスクがあるとします。

b-tree の構築方法 log2 高さ = number_of_tree 要素

最も重要な

したがって、Bツリーがどのように構築されるかによって、すべてのN個の要素で要素を見つけるために「高さ」以上の操作は必要ありません。

したがって、log2 N_number_of_tree_elements ..またはlog(N)が必要です。

于 2013-01-13T09:06:28.277 に答える
0

私にとって、このような問題を理解するには、これが良い考え方です。

于 2011-05-02T00:13:12.307 に答える
0

O(log(n)) が何を意味するかを理解するには、Big O notaionを読みたいと思うかもしれません。つまり、データセットが 1024 倍大きくなると、実行時間は 10 倍 (またはそれ以下) (基数 2 の場合) になります。

MergeSort は O(n*log(n)) で実行されます。つまり、10 240 倍の時間がかかります。バブル ソートは O(n^2) で実行されます。つまり、1024^2 = 1 048 576 倍の時間がかかります。だから、本当に安全になる時間があります:)

合計を理解するには、マージソート アルゴリズムをツリーとして見る必要があります。

         sort(3,1,2,4)
        /            \
   sort(3,1)      sort(2,4)
    /     \        /     \
sort(3) sort(1) sort(2) sort(4)

合計は、ツリーの各レベルで繰り返されます。k=0 が上、k= log(n) が下です。ツリーの高さは常に log2(n) になります (バランスの取れたバイナリ ツリーであるため)。

少し計算するには：

Σ 2^k * 2(n/2^k) = 
2 * Σ 2^k * (n/2^k) =
2 * Σ n*2^k/2^k = 
2 * Σ n = 
2 * n * (1+log(n)) //As there are log(n)+1 steps from 0 to log(n) inclusive

もちろん、これは、特により複雑なアルゴリズムを使用している場合は、多くの作業を行う必要があります。そのような状況では、マスター定理に本当に満足していますが、今のところ、それはあなたをもっと混乱させるかもしれません. 非常に理論的なので、すぐに理解できなくても心配はいりません。

于 2011-05-01T16:54:45.013 に答える