n^2 + T（n-1）に対して、この単純なアルゴリズムT（n/2）+1の最悪の場合の時間の複雑さはなぜですか？
次の質問は最近の大学の課題です。私は、n^2が漸近時間の複雑さO（n^2）になると思ったので、答えがn^2 + T（n-1）であると思ったでしょう。 T（n/2）+1と同様に、その漸近時間の複雑さはO（log2（n））となる。
回答が返され、正解がT（n/2）+1であることが判明しましたが、なぜこのような場合に私の頭を浮かべることはできません。
誰かが私にこのアルゴリズムの最悪の場合の時間の複雑さを説明することができますか？時間の複雑さの私の理解はちょうど間違っている可能性があります。
漸近時間の複雑さは、nを大きく取っています。あなたの例の場合、質問ではkが固定であると指定されているので、関連する唯一の複雑さが最後のものです。具体的には、Wikipedia formal definitionを参照してください：
nは、無限大にT(n) = T(n/2) + 1を支配再帰を成長するにつれて。基本的にx_0 = 10 * kを選択し、最初の2つのケースを使用して有限のMが見つかることを証明する正式な定義を使用して証明できます。 log(n)とn^2の両方がこの定義を満たしていることは明らかです。したがって、より厳密な境界は漸近的複雑さです。
O（f（n））はどういう意味ですか？それは時間が最大でc * f（n）であることを意味します。
kevmoはO（log2 n）の複雑さを主張しました。あなたはすべての値n≤10kをチェックし、T（n）の最大値をXとすることができます.Xはかなり大きいかもしれません（この場合は約167k^3ですが、 ）。より大きいnの場合、必要な時間は最大でX + log2（n）です。 c = Xを選ぶと、これは常にc * log2（n）よりも小さくなります。
もちろん、人々は通常、O（log n）アルゴリズムは高速であると想定していますが、k = 10,000の場合はこれが最も確実です。だから、O表記は注意深く扱わなければならないことも学んだ。
ありがとうございます！ kが固定されているという意味が、関連する唯一の複雑さが最後のものであることを意味するのであれば、あなたは少し詳しく説明できますか？私はwiki上の正式な定義を読んでいますが、私はまだこの記述が本当の理由を理解していません。 –
'k 'が固定されていない場合、' x_0 = 10 * k'を選択することができます。これは定義を満たす有限の 'M'を生成します。 'k'が固定されていない場合、' k'は常に敵によって大きく選択されるので、 'x_0'は存在しない可能性があります。したがって、有限の' M'は必ずしも見つけることができません。 – kevmo314