math - 分割統治

Question

Divide and Conquer について学んでいますが、1 つの概念を理解するのに苦労しています。ソートされた配列があり、何らかのタスクを実行したい場合....式を取得します

T(n) = a (n/b) * O(n)

そして、b = 2(binary tree) を使用すると、各サブ配列がさらに 2 つのサブ配列になることを意味します...

T(n) = 2 (n/2) * O(n)--> そしてマスタールールにより、running time = O(n * logn)

ここでb = 3(tri-nary tree) を使用すると、各サブ配列がさらに 3 つのサブ配列になることを意味します。

T(n) = 3 (n/3) * O(n)--> つまり、running time = O(n * logn)

質問：

分割数を増やすと、実行時間は長くなりますか?

ツリーがどんなに大きくても、同じ実行時間を取得し続けるのはなぜですか?

Answer 1

このように考えてください。長さのn配列があります。ツリーの各レベルで、その配列を再分割します。しかし、nどのように細分化しても、全体として要素は存在します。

親レベルでは、n作業を行います。あなたはそれぞれの子供でn/X仕事をしますが、あなたはそれをX何度もしますn。

Answer 2

簡単です。ツリーの次数に関係なく、次のレベルのプロセスの合計は同じです。ご存知のように、ツリーの次数が大きいほど、子ノードでのプロセスは小さくなります。また、次のレベルのプロセスの合計も同じです。ただし、アイドル状態でのみ有効です。実際には、再帰関数呼び出しのため、ツリーの次数が多いほど、ツリーの次数が少ない場合よりも実行時間が遅くなります。