[알고리즘] 2. 시간복잡도

1. 시간복잡도

문제가 얼마나 빠르게 해결되는지 나타냄
대략적으로 몇개의 명령을 수행하는지?

1.1 for문

1
2
3

for(int i=0 ; i<n; i++){
  int a=0;
}

int a=0;명령을 n번 수행 >> 시간복잡도 O(n)

1.2 n*n 이중for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  for(int j=0 ; j<n; j++){
    int a=0;
  }
}

int a=0;명령을 n*n번 수행 >> 시간복잡도 O(n^2)

1.3 n(n-1)(n-2) …2*1 이중for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  for(int j=0 ; j<i; j++){
    int a=0;
  }
}

int a=0;명령을 n(n-1)/2번 수행 >> 1/2nn >> 상수는 무시 >> 시간복잡도 O(n^2)

1.4 if절 있는 for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  if(i==1){
    int a=0;
   }
}

최악의 경우 n번 수행(if절 결과에 따라) > O(N)
최고차항만 체크

2. 입력크기에 따른 수행시간

1. n의 입력 값에 따라 수행시간 다름
2. 컴퓨터 사양에 따라 다름

2.1 O(N) 시간복잡도

• n이 9000만개일때 보통 1초

2.2 O(N^2) 시간복잡도

• n이 10000개일때 보통 1초 > 명령어 실행수 대략 1억에 1

3. 정렬의 시간복잡도

3.1 선택정렬

최소값 1번 찾는데 O(N)번 * N번 > O(n^2)

3.2 삽입정렬

원소 하나 삽입 시 O(N)걸림 * N번 > O(n^2)

3.3 버블 정렬

인접한 원소 비교해서 뒤로 보냄 O(n) 걸림 * n번 > O(n^2)

• 선택, 삽입, 버블 정렬은 시간복잡도가 안 좋은편!!