아래의 의사 코드에 대한 정확한 응답과 점근 적 응답을 모두 제공하십시오.

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))이어야합니다.

시스템에 따라 크게 달라질 수 있으므로 실행 시간을 정확하게 예측할 수 없습니다.