次のアルゴリズムがあるとします。
procedure(n)
if n == 1 then break
R = generaterandom()
procedure(n/2)
これで、このアルゴリズムの複雑さはわかりましたが、ランダムジェネレーターlog(n)
を呼び出しますか、または呼び出しのために呼び出されないためです.log(n)
log(n)-1
n==1
これが明らかである場合は申し訳ありませんが、私は周りを見回しており、正確な答えがどこにも述べられていません.