시간 복잡도(Time Complexity)

728x90

SMALL

[시간 복잡도]

알고리즘이 실행되는 데 걸리는 시간은 컴퓨터가 알고리즘 코드를 처리하는 속도에 의존할 수밖에 없다.

그리고 이 속도는 운영체제, 하드웨어, 프로그래밍 언어, 컴파일러 등 실행 환경에 따라 달라질 수 있다.

그러므로 알고리즘의 성능을 평가하기 위해 입력크기에 따라 컴퓨터가 수행하는 연산의 횟수를 수치화시킬 필요가 있다.

시간복잡도는 이렇게 수치화된 값을 가지고 알고리즘 수행시간 및 성능을 나타낼 수 있는 지표이다.

당연히 시간 복잡도의 수치가 작으면 작을수록 더 효율적이고 성능 좋은 알고리즘이 된다.

시간복잡도는 알고리즘의 복잡도를 단순화시켜 입력값의 크기에 따른 증감 추세를 점근적으로 나타낸다.

이러한 기법을 점근 표기법이라고 한다.

일반적으로 우리가 알고 있는 시간 복잡도는 점근 표기법을 이용하여 나타낸다.

점근적 표기법은 크게 3가지로 볼 수 있다.

ㄴ오메가(Ω) 표기법 : 시간 복잡도가 최상의 경우

ㄴ세타(ω) 표기법 : 시간 복잡도가 평균의 경우

ㄴ빅오(O) 표기법 : 시간 복잡도가 최악의 경우

우리는 항상 알고리즘이 최악의 경우를 고려하여 판단을 해야 하기에 빅오 표기법이 자주 쓰인다.

Big-O 표기법은 최고차항보다 상대적으로 영향력이 적은 낮은 차수의 항과 상수를 무시하고 표기한다.

ㄴO(2N+5) => O(N)

ㄴO(3N^2+531) => O(N^2)

ㄴO(4) => O(1)

728x90

LIST