이 코드의 시간 복잡도는 무엇입니까?

Question

이 수행되는 방법

  Input: n (pos. Integer) 
      Output: y (pos. Integer) 
      Other: x, z (pos. Integer) 
       y := 0; 
       x :=0; 

       while x < n do 
         y := y + 1; 
         z := 0; 
         while z < 4 do 
          x := x + 1; 
          z := z + 1; 
         end; 
         for (i=0;i<2;i++){ 
          x=x-1; 
         } 
       End; 

을 시작? 나는 for 루프가있을 때 O (N)이고 잠시있을 때는 O (log N)임을 알고있다. 내가 도움 :

당신

Answer 1

이 작업을 수행하는 좋은 방법 감사 감사하겠습니다은 반복 당 않습니다 얼마나 많은 시간을 외부 루프가 실행하는 방법과 많은 일을 결정하는 것입니다.

루프의 본체는 다음 두 번째 마찬가지로

  y := y + 1; 
      z := 0; 
      while z < 4 do 
        x := x + 1; 
        z := z + 1; 
      end; 
      for (i=0;i<2;i++){ 
        x=x-1; 
      } 

첫 번째 라인은, O (1) 작업을한다. 논리의 다음 부분은 네 번 실행되는 루프이며 각 반복은 O (1) 작업을 수행합니다. 따라서,이 내부 루프는 O (1)을 수행합니다. 마지막으로 나머지 루프는 O (1) 작업을 수행합니다. 결과적으로, 루프의 각 반복은 O (1)을 작동시킵니다.

외부 루프는 몇 번 실행됩니까? 루프가

while x < n do 

x는 0에서 시작하고 각 반복마다 x가 4 회 증가하고 x가 두 번 감소한다는 점에 유의하십시오. 결과적으로 루프의 반복마다 x는 2 씩 증가합니다. 따라서 루프 반복 횟수는 대략 n/2 = O (n)입니다.

루프가 O (n) 번 실행되고 반복마다 O (1)이 작동하므로 여기에서 수행 된 총 작업은 O (n)입니다.

희망이 도움이됩니다.