algorithm - アルゴリズムの複雑さ、再帰方程式の解法

Question

私はデータ構造とアルゴリズムのコースを受講していますが、次の再帰方程式に行き詰まっています。

T(n) = logn*T(logn) + n

明らかに、これはマスター定理を使用して処理することはできないので、誰かがこの再帰方程式を解くためのアイデアを持っているかどうか疑問に思っていました. n を 2^m と見なすなど、パラメーターを変更して解決する必要があると確信していますが、適切な修正を見つけることができませんでした。

Answer 1

これは決して公式の証明ではありませんが、このようになると思います。

鍵は+ nパーツです。このため、Tは で下に制限されo(n)ます。(それともビッグ オメガでしょうか? 私は錆びています。) では、それを想定して試してみましょうT(n) = O(n)。

元の関係に代入

T(n) = (log n)O(log n) + n
     = O(log^2(n)) + O(n)
     = O(n)

だからそれはまだ保持されます。