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)).

您无法准确估计运行时间，因为它高度依赖于您的系统。