algorithm - アルゴリズムの複雑さを決定する

Question

algo(p) は、実行に Theta(p) 時間を要し、p を変更しないアルゴリズムであると仮定します。次のアルゴリズムの実行時間の複雑さを決定します。

Algo2(n) 
begin
p=1;
while p <= n 
    begin 
    algo(p)
    p=2*p
    end;
end;

どこから始めればよいのか本当にわかりません。おそらく p=p*2 から O(logn) を考えていましたが、while ループに algo(p) があり、それがどのように影響するかわかりません。

score 0 · Accepted Answer

問題をより簡単にするために、次のように設定できます。

Algo(n)
  begin
  p=1, i=1
  while p<= n
    begin
    algo(p)
    p=2*p
    i++
    end
  end

そのように書き換えることができます：

Algo(n)
  begin
  i=1
  while 2^(i-1)<=n
    begin
    algo(2^(i-1))
    i++
    end
  end

次に、ヘンリックが言ったように：

p = 1, 2, 4, ..., 2^(floor(logn)) で algo(p) O(logn) 回呼び出します。これは Theta(1 + 2 + ... + 2^(floor(logn)) = Theta(2^(floor(logn+1)-1) = Theta(n)) です。

2 に答える 2