시간복잡도란?

대강 뜻만 알면 되겠지 하고 자세히 알아본 적이 없었네요.

자세히 살펴보겠습니다.

어떠한 알고리즘의 자원의 사용량을 분석하는 것은 중요한 이슈입니다.

얼마나 잘 짜여져 있는지 확인할 수 있는 지표이기 때문이죠.

여기서 자원이란

실행 시간, 메모리, 저장장치, 통신 등 말 그대로

해당 알고리즘을 돌리는데 사용되는 모든 재료를 말합니다.

이러한 여러가지 자원 중 표현하기 가장 좋은 것이 실행시간이겠죠.

하지만 실행시간으로 자원의 사용량을 나타내기에는 문제점이 있습니다.

실행시간은 하드웨어, 운영체제, 언어, 컴파일러 등 실행 환경에 따라서 달라지기 때문입니다.

따라서 환경에 구애받지 않는 관측도구를 사용한 점근적인 접근이 필요한데,

이것이 바로 시간복잡도입니다.

다시말해 시간복잡도는,

실행시간 대신 연산의 실행횟수를 카운트해 

알고리즘의 자원의 사용량을 간접적으로 나타내는 것을 말합니다.

조금 더 구체적으로는 

데이터가 n -> ∞로 증가하는 만큼 늘어나는 연산의 실행횟수를

O-표기, Ω-표기, θ-표기 등의 함수형태로 나타냅니다.

O-표기

• 최고 차항의 차수만 표시
• '최악의 경우 이 횟수가 나온다(upper bound)'는 의미 -> 따라서 가장 보편적으로 사용

Ω-표기

• 최저 차항의 차수만 표시
• '최선의 경우 이 횟수가 나온다(lower bound)'

θ-표기

• 위 두 구간의 교집합