오리엔테이션 : 시간복잡도 계산

시간복잡도 : 내 프로그램이 수행하는 연산의 수를 수식으로 나타낸 것

 

보통 빅오(O) 표기법을 사용하는데 이는 최악의 경우를 기준으로 계산한다.

 

for문

 

int ex(n){
 int x = 0;
 for(int i = 0;i<n;i++){
   x += i;
   System.out.println(x);
   }
   }

위 함수의 시간복잡도는 2n번 연산하기 때문에 O(n)이다. 

for문 안에서 2번의 연산을 하니까 O(2n)이라고 생각할 수도 있지만, 시간복잡도에서의 계수는 1이며(1/2n 도 n), 수식으로 나타낸 것이 다항식일 때에는 가장 높은 차수를 사용하므로(n^2 + n 은 n^2) O(n)이다.

 

int ex(n,m){
 int x = 0;
 for(int i = 0;i<n;i++){
   for(int j = 0;j<m;j++){
     System.out.println(x);
   }
   }
   }

 위의 경우는 nm번 수행하므로 시간복잡도는 O(nm)이다.

 

while문

 

int ex(n){
  while(0 > n || n > 100){
     if(n < 0)  n++;
     else  n--;
     return n;
     }

while문은  for문에 비해 생각할 것이 많다. 

경우의 수를 세가지로 나누면

• n이 음수인 경우 ( -n)
• n이 0에서 100 사이 (1)
• n이 100보다 크다(n-100)

이다. 이때 가장 큰 차수는 n이므로 시간복잡도는 O(n)이다.

 

예시

 

void ex(int n, int m){
  int k = 0;
  int[] vis = new vis[n][m];
  for(int i =0;i<n;i++){
     for(int j = 0;j<m;j++){
        if(vis[i][j] == 0){
          for(int  k = 0;k<m;k++){
           vis[i][j] = 1;
           }
           }
           }
           }
           }

이 함수는 언뜻보면 nmk 같지만 k를 이용하는 for문에서 j 가 0일 때 vis 한 줄을 1로 만들면 다음 부터는 이 for문이 돌지 않는다. 따라서 시간복잡도는 O(nm)이다.

 

시간 계산하기

 

for 문이 1억번 돌 때 1초가 걸린다. 이를 바탕으로 n이 주어졌을 때 어느정도의 시간복잡도를 가진 알고리즘을 사용할 수 있을지 생각 할 수 있다.

원래 시간초과 때문에 시간 많이 빼았겼었는데 위 공식 잘 외워서 써야겠다.

 

 

공간복잡도

 

공간복잡도는 크게 어렵지 않다.

int[] arr = new int[n][n];

이 경우 공간복잡도는 O(n^2)이다.

 

또한 

int[][][] arr = new int[n][n][n];

이 경우의 공간복잡도는 O(n^3)이다.