시간 복잡도 (Time complexity)

시간복잡도란?

• Time complexity란 문제를 해결하기위한 연산 횟수
•  특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
• 1억번의 연산 횟수를 1초의 시간으로 간주

시간복잡도의 유형

• Big-Ω(빅 오메가) : 최선
• Big-θ(빅 세타) : 보통
• Big-O(빅 오) : 최악 (코테에서는 빅오 표기법 사용권장)

▶ 빅오표기법의 성능 비교
효율성 : O(1) > O(log n) > O(n) > O(n x log n) > O(n^2) > O(2^n) 
            [fast]( 상수함수 > 로그함수 > 선형함수 > 다항함수 > 지수함수 )[slow]


▶ 빅오표기법 예제
    1. O(1): Operation push and pop on Stack
    2. O(log n): Binary Tree
    3. O(n): for loop
    4. O(n×log n): Quick Sort, Merge Sort, Heap Sort
    5. O(n2): Double for loop, Insert Sort, Bubble Sort, Selection Sort
    6. O(2n): Fibonacci Sequence(수열)

▶ 연산횟수 계산법 : 시간복잡도 * 데이터 크기
     N개의 수가 주어질 때,  오름차순 정렬 알고리즘을 만드세요.
    (제한시간 2초, 데이터수 : 백만개)
   
     위의 문제에서 2초의 제한 시간이면 2억번의 연산횟수 안에 답을 내야한다.
     아래 1,2번중 병합정렬로 문제를 풀면 시간내에 연산처리가 가능하다.
      1. 버블정렬[ O(N2) ] : (백만)의 제곱이므로,  2억번의 횟수를 훨씬 넘는다. 시간내 처리 불가능.
      2. 병합정렬[ O(n×log n) ] : 2억번의 횟수보다 작으므로, 시간내 처리가 가능.

 

빅오표기법 차트

 

 

 

결과적으로 코드작성(문제풀이)시 고려할점?

 
   더 짧은 시간안에(시간복잡도) 더 적은 메모리(공간복잡도) 문제를  해결하는 코드를 작성해야함. 

1. 알맞은 알고리즘을 선택했는지?(시간복잡도를 고려하여 제한시간 내에 수행가능한 알고리즘 선택)
2. 비효율적인 코드확인 후 수정(가장 많이 중첩된 중복문을 기준으로 확인)
   
   
   

int num = 100;

/* 
  다수의 포문을 돌리는것이 이중반복문 보다 효율이 나을 수 있다.
*/ 

// 다수의 포문. 총 300번 수행
for(int i=0; i<num; i++){
 	// 100번 수행
}
for(int i=0; i<num; i++){
 	// 100번 수행
}
for(int i=0; i<num; i++){
 	// 100번 수행
}

// 하나의 이중 포문 
for(int i=0; i<num; i++){
	for(int j=0; j<num; j++){
    	// 100*100 번 수행하므로 더많이 수행.
    }
}