次のアルゴリズムの実行時間をO表記で定義するのに苦労します。私の最初の推測はO（n）でしたが、反復と私が適用する数の間のギャップは安定していません。どのように私はこれを間違って定義しましたか？解決：T（n）= T（n/2）+ n/2 + 1
public int function (int n)
{
if (n == 0) {
return 0;
}
int i = 1;
int j = n ;
while (i < j)
{
i = i + 1;
j = j - 1;
}
return function (i - 1) + 1;
}
while約n/2時に実行されます。
再帰ので、nとしてオリジナルnの約半分の値を渡して実行される：
n/2 (first iteration)
n/4 (second iteration, equal to (n/2)/2)
n/8
n/16
n/32
...
これはgeometric serieと同様です。
InfactはそうそうO表記はO（N）
別のアプローチは、T(n) = T(n/2) + n/2 + 1としてそれを書き留めすることであるn * 1 = n
に収束
n * (1/2 + 1/4 + 1/8 + 1/16 + ...)
として表すことができます。 。
whileループはn/2の作業を行います。次の呼び出しに渡される引数はn/2です。
Let c=0.9
1*(f(n/2) + 1) <? c*f(n)
1*(n/4)+1 <? 0.9*(n/2 + 1)
0.25n + 1 <? 0.45n + 0.9
0 < 0.2n - 0.1
：
T(n) = Θ(n)
正確には、ビット-Oは、上限のためのものであるので、多くの可能な答えがあります。たとえば、このアルゴリズムがO（n * n）であると言うと、それは真実ですが、誤解を招きます。可能であれば、ビッグ・シータを使用して実行時間を記述することが通常は良い方法です。受け入れられた答えの分析は、ビッグ・シータに対しても同様に有効です。 –