algorithm - マスターの定理を使用して t(n)=2t(n/2)+n^0.5/logn を解くことができますか?

Question

私は友人と口論しています.昨日試験がありました.私はそれができないと言った.彼はそれがケース1になると言った.おそらく彼は正しい. 前もって感謝します。

Answer 1

n の値が 1 より大きい場合、n^(0.5/log n) は exp(0.5) の定数値を持ちます。これは非常に簡単に証明できます。

   x = n^(0.5/log n)
   log(x) = (log n) * 0.5 / (log n) = 0.5
=> x = exp(0.5) = 1.64872...

その結果、式の第 2 項は定数として扱うことができます。定数の第 2 項を使用すると、数式はt(n) = 2t(n/2) + 1と等価になり、複雑さは O(n) になります。

はい、あなたの友人は正しいです。これは、f(n) ∈ O(n^c) の c の値がゼロであるケース 1に対応します。