2
A
答えて
4
あなたはおそらく、T(n)=T(⌊n/2⌋)+ T(⌈n/2⌉) + 1
です。
T(n)
の最初のいくつかの値を計算します。
T(1) = 1
T(2) = 3
T(3) = 5
T(4) = 7
T(n) = 2 * n - 1
と推測できます。
根拠
T(1) = 1
T(2) = 3
T(3) = 5
T(4) = 7
誘導ステップ
T(2*n) = T(⌊2*n/2⌋)+ T(⌈2*n/2⌉) + 1
= T(⌊n⌋)+ T(⌈n⌉) + 1
= (2*n - 1) + (2*n - 1) + 1
= 4*n - 1
= 2 * (2*n) - 1
T(2*n+1) = T(⌊(2*n+1)/2⌋)+ T(⌈(2*n+1)/2⌉) + 1
= T(n)+ T(n+1) + 1
= (2*n - 1) + (2*(n+1) - 1) + 1 =
= 4*n + 1 =
= (2*n+1)*2 - 1
によって基礎と誘導ステップの両方が証明されているのでことを証明、それは今数学的帰納法によって証明されていますT(n)は全ての自然の2 * n - 1に対して成り立つことを意味する。
T(n) = 2*n - 1 = O(n)
+0
+1。本当によく説明されています! –
0
現在のところあなたは何が理にかなっていません。 n
は通常自然数と解釈されるので、n=⌊n⌋=⌈n⌉
となります。その再発は、サイズn
の問題をサイズn
という2つの問題に分解し、その間に1
を費やします。作成した2つの新しい問題は、順番に分割されるなど、あなたがしているのは自分自身でさらに多くの作業を作成することです。
あなたは係数をどこか忘れてはいけないと確信していますか? T(⌊n/2⌋)の係数「2」?あなたの再発はあまり意味がありません。 – pad
この再帰は決して収束しません – mbatchkarov
しかし、私は下限と上限をその式でも持っています – Luv