宿題で次の再帰関係を解くように言われました T(n) = T(√n) + T(n - √n) + cn
これが私が同じことを解決し、正しい答えを得た方法です。しかし、私の解決には明らかな誤りがあります。私の間違ったステップを修正する方法を指摘してください。
すべての n > 4 に対して、√n < (n-√n)
したがって、項 T(n - √n) は T(1) に向かってゆっくりと移動し、再帰ツリーの高さに寄与します。
簡単な数学では、√n 回の反復の後、項 T(n - √n) は最終的に T(1) になると言えます。(これは私が間違っていたところです。項は T(n - √n) 、T(n - 2√n)、T(n - 3√n) のように短縮されると思っていましたが、そうではありません)
したがって、上の木の高さは √n です。
また、各レベルでの運用コストは最大で cn です。
したがって、操作の総コストは √n * cn です。
したがって、アルゴリズムの実行時間は O(n√n) です。