[Do it! 강의 정리] 시간복잡도

알고리즘 선택의 기준이 되는 시간 복잡도

 

시간복잡도 강의

시간 복잡도 표기법

시간 복잡도 : 주어진 문제를 해결하기 위한 연산 횟수

• 파이썬에선 2,000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측됨

시간 복잡도 유형

빅-오메가 Ω(g(n))	최선일 때의 연산 횟수를 나타낸 표기법 (best case)
빅-세타 θ(g(n))	보통일 때 연산 횟수를 나타낸 표기법 (average case)
빅-오 O(g(n))	최악일 때 연산 횟수를 나타낸 표기법 (worst case)

코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.

 

시간 복잡도 그래프

 

빅오 표기법의 시간 복잡도

데이터의 크기가 클수록 기하급수적으로 커짐

시간 복잡도 활용하기

알고리즘 선택 기준으로 활용하기

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

입력
1번째 줄에 개수 N(1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

출력
1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

시간제한 : 2초

최악의 케이스는 2초에 4천만 번이므로, 4천만 번 이하의 연산 횟수로 문제를 해결해야 함

 

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 n 값에 데이터의 최대 크기를 대입해 도출

 

알고리즘 적합성 평가

• 버블 정렬 = (1,000,000)^2 > 4,000,000 -> 부적합 알고리즘
• 병합 정렬 = 1,000,000log_2(1,000,000) < 4,000,000 -> 적합 알고리즘

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준