알고리즘의 효율 분석에 관하여

개념

시간 복잡도 (time complexity)

알고리즘의 성능을 나타내는 지표, 입력 크기에 대한 연산 횟수의 상한을 의미

• 낮으면 낮을 수록 좋다

 

• 입력 크기
  • 알고리즘이 처리해야 할 데이터 양

 

시간 복잡도 측정법

시간 복잡도 : 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수

• 측정 결과 : 최선(best), 보통(normal), 최악(worst)

 

점근적 표기법

• 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법

 

빅 오 표기법(big-O notation)

• 최악의 경우를 가정하고 시간 복잡도를 표현하는 방법
• 데이터 개수 N에 대해 연산 횟수를 일반화한 후 최고차항을 남기고 차수를 제거한다

 

최고차항 남기는 작업의 우선순위

함수 종류	예
지수함수	2^x
다항함수	3x^2
로그함수	logx

지수함수 > 다항함수 > 로그함수

 

 

시간 복잡도를 코딩 테스트에 활용하는 방법

문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해보자 !

• 연산 횟수 : 1000 ~ 3000만 정도로 고려하기

 

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20 ~ 25
O(N^3)	200 ~ 300
O(N^2)	3000 ~ 5000
O(NlogN)	100만
O(N)	1000 ~ 2000만
O(logN)	10억

 

 

시간 복잡도 계산해보기

순서

1. 문제 정의
2. 연산 횟수 측정
3. 시간 복잡도 분석

 

문제를 풀 때, 특정값을 계속 반으로 줄이는 동작을 한다 -> 시간 복잡도 O(logN)