코딩 테스트 합격자 되기 - 시간복잡도

알고리즘 이란?

알고리즘은 문제 해결을 위한 처리 과정을 단계적으로 나열한 것.

 

알고리즘은 다음 조건을 만족한다.

• 입출력 : 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 한다.
• 정밀성 : 변하지 않는 명확한 작업 단계가 있어야 한다.
• 유일성 : 단계별로 명확한 다음 단계가 있어야 한다.
• 타당성 : 구현할 수 있고 실용적이어야 한다.
• 유한성 : 한정된 수의 단계를 거친 후 반드시 종료해야 한다.
• 일반성 : 모든 케이스에서 사용할 수 있어야 한다.

---

 

점근성능

입력의 크기가 커질수록 알고리즘의 수행 시간은 증가한다.

입력 크기 n이 무한히 많아지는 상황을 전제로 알고리즘을 파악하여 성능을 표현해야한다.

n이 커짐에 따라 결정되는 성능이 점근성능이다.

점근성능은 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 단순화시킨 형태가 된다.

 

점근성능 표기법

다항식에서 가장 많이 영향을 미치는 항을 남기고 나머지는 제거한다.

마지막 남은 항의 계수를 제거한다.

O-표기

• O-표기는 g(n)을 상한으로 간주하기 때문에 함수의 점근적 상한을 나타낸다.
• 입력 크기 n이 증가함에 따라 알고리즘의 최악의 수행 시간은 g(n)에 비례해서 증가한다.

O-표기 연산 횟수

입력 크기 n이 증가하더라도 수행 시간이 상대적으로 적게 증가하는 알고리즘을 알맞게 선택해야한다.

O(N!)	O(2N)	O(N3)	O(N2)	O(NlogN)	O(N)	O(logN)
10	20-25	200-300	3,000-5,000	100만	1,000~2,000만	10억