3

マスター定理をどのように理解するか、アルゴリズムは次のように再帰的に定義できます。

a T(n/b) + O(n^d)

ここで、a は部分問題の数、n/b は部分問題のサイズ、O(n^d) は部分問題の再結合時間です。マスター定理の時間計算量を計算すると、次のようになります。

T(n) =  { O(n^d)                    if d > log base b of a
        {
        { O(n^d log n)              if d = log base b of a
        {
        { O(n^ (log base b of a) )  if d < log base b of a

私の質問は、再結合時間が O(n^d) の形式で表現されていない場合はどうなるでしょうか? O(2^n) や O(log(n)) など。時間の複雑さをどのように決定しますか?

4

1 に答える 1

2

マスター定理では、特定の形式の繰り返しにのみ適用されます。あなたは言う：

マスター定理をどのように理解するか、アルゴリズムは次のように再帰的に定義できます。

しかし、これは完全に正確ではありません.あなた自身が示したように、すべてのアルゴリズムがそのように再帰的に定義できるわけではありません. マスター定理は、そのように定義できるものにのみ適用されます (より具体的には、適用できるすべてのケースについてはこちらを参照してください)。

他の形式については、このような他の定理があります。

于 2013-05-17T00:23:20.767 に答える