1

T(n)=T(n/2)+sqrt(n) が O(sqrt(n)) であることを証明しようとしています (T(1)=1 の場合、誘導のみを使用)。マスター定理を使えば簡単に解けますが、そうではありません。仮定してみました

T(n/2) < c*sqrt(n/2)

しかし、証明の残りの部分ではあまりうまくいきませんでした。ご回答いただきありがとうございます。

編集：私の解決策（上記の仮定の後）は次のとおりです。

T(n) <= c*sqrt(n/2)+sqrt(n) = sqrt(n) (c/sqrt(2)+1) <= sqrt(n) (c+1)

これから必要なものに移動する方法がわかりません

T(n)<=c*sqrt(n)

4

2 に答える 2

3

わかりました、あなたは近くにいます。基本的に、コメントで述べたように、基本ケースは単純です。誘導の場合、T(n/2) が O(sqrt(n/2)) であるとすると、T(n) が O(sqrt(n)) であることを示します。

したがって、次のようになります。

T(n) = T(n/2) + sqrt(n)               ; this is just your recurrence
     < c sqrt(n/2) + sqrt(n)          ; since T(n/2) is O(sqrt(n))
                                      ; wlog here, assume c > 4
     = c sqrt(n) / sqrt(2) + sqrt(n)
     = (c/sqrt(2) + 1) sqrt(n)

c > 4 の場合、c / sqrt(2) + 1 < c なので、

(c/sqrt(2) + 1) sqrt(n) < c sqrt(n)

それで

T(n) < c sqrt(n)

したがって、T(n) は O(sqrt(n)) です。

ここで、見逃した重要なポイントがいくつかあります。

1 つ目は、いつでも c を任意の値に増やすことができるということです。これは、大きな O は < しか必要としないためです。< cf(n) の場合は < df(n) であり、d > c.

2 つ目は、線 f(c) = c/sqrt(2) + 1 が c = sqrt(2) / (sqrt(2)-1) = 3.4143 付近で線 f(c) = c と交差することに注意することです。 (またはそう)、したがって、(c/sqrt(2) + 1) < c を取得するには、c を強制的に > この値にするだけです。4 は確かに機能するので、4 の由来です。

振り返ってみると、キーポイントをヒントとして与えるべきでした。私のせいです。ごめん！

于 2013-01-28T22:56:30.767 に答える
1

役立つかもしれない考え方の 1 つは、再帰を再帰的に展開することです。あなたが得る

T(n) = sqrt(n) + sqrt(n/2) + sqrt(n/4) + ... + sqrt(n/(2^k)) + ... + sqrt(1)
     = sqrt(n) + sqrt(n)/sqrt(2) + sqrt(n)/sqrt(4) + ... + sqrt(n)/sqrt(2^k) + ... + sqrt(1)
     = sqrt(n) * (1 + sqrt(1/2) + sqrt(1/2)^2 + ... + sqrt(1/2)^k + ...)
     <= sqrt(n) * ∑(k=0 to ∞) sqrt(1/2)^k
     = sqrt(n) * 1/(1 - sqrt(1/2))

1/(1-sqrt(1/2))は有限定数 (約 3.4) であるため、 である必要T(n)がありますO(sqrt(n))。この情報を使用して、標準帰納法を使用して証明できます。

于 2013-01-28T23:20:20.630 に答える