time - 以下の疑似コードの正確な答えと漸近的な答えの両方を与えてください

Question

for i <--- 1 step i <--- 2* i while i< n do 
  for j <--- 1 step j <---2* j while j<n do 
    if j = 2*i 
      for k = 0 step k <--- k+ 1 while k < n do 
        .... CONSTANT NUMBER OF ELEMENTARY OPERATIONS 
      end for 
    else 
      for k<--- 1 step k<-- 3*k while k<n do 
        ...CONSTANT NUBER OF ELEMENTARY OPERATIONS 
      end for 
    end if 
  end for 
end for

n の関数として次のコード フラグメントの実行時間は?

「正確な答え」とは、漸近的な実行時間を決定する前に、コードに関連する方程式を指します。

Answer 1

宿題のように聞こえますが、いくつかの考慮事項を考慮すると、その疑似コードの漸近的な複雑さはO(n*log(n)).

システムに大きく依存するため、実行時間を正確に見積もることはできません。