알고리즘의 시간복잡도(Big-O)
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다.
- wiki
알고리즘의 성능 계산
알고리즘의 성능을 계산하는 것에 있어 단순히 아웃풋이 나오는 결과의 시간 을 측정하는 것은 모든 경우에 적용되지 못한다. 이유는 해당 알고리즘을 실행하는 하드웨어와 소프트웨어 환경이 모두 상이하여 같은 성능을 가질 수 없기 때문이다. 따라서 알고리즘을 측정하는 객관적인 단위는 실행되는 단계(step)을 기준으로 한다.
단계는 메모리 기본연산(대입, 복사, 산술연산 등)이다. 기본연산은 1단위 시간을 기준으로 하며 이런 단위를 적용할 수 있는 언어를 사용해 알고리즘의 성능을 표현할 수 있다.
즉, 1단위 == 단계 == 메모리의 기본연산이라고 볼 수 있다.
시간복잡도
알고리즘의 성능을 단위를 기준으로 한다면, 단위와 시간으로 알고리즘의 성능을 유추할 수 있다.
그렇다면 알고리즘의 성능은 어떻게 계산을 할 수 있을까?
어떤 입력 값을 넣었을 때 항상 같은 시간을 보장하는 알고리즘은 거의 찾을 수 없다. 따라서 보통 알고리즘의 성능은 최고성능, 평균, 최악의 성능 이 3가지 시간복잡도로 분류한다. 가장 좋은 지표로 삶을 수 있는 것은 알고리즘의 평균 시간복잡도이겠지만, 단위와 시간으로 성능을 구할 수 있다 하더라도 모든 입력 값에 대한 시간에 대한 평균값을 구하는 것은 굉장히 복잡하고 번거롭다. 그래서 현실적으로 사용하기 용이한 가장 안좋은 시간복잡도를 사용한다.
가장 오래걸리는 입력(Worstcase Input)을 사용해 최악의 성능을 보여주는 시간복잡도를 사용한다.
최악의 기준(Worstcase Time Complexity)은 정확한 값은 아니지만 알고리즘의 성능을 그만큼 보장한다.
어떤 입력 값을 넣어도 적어도 이 성능을 보장한다는 의미이다.
Big-O 표기법
시간복잡도를 사용해서 알고리즘의 성능을 계산했다면, Big-O는 알고리즘의 성능을 수학적으로 나타내는 표기법이다. 실제 실행 시간을 표기하는 것이 아닌 입력 값 증가에 따른 알고리즘의 성능 예측에 중점을 두고 있다.
Big-O표기법은 낮은 차수와 항을 제외하고 최고차항만 남겨 표기한다. 이런 표기법을 사용하는 이유는 입력의 크기가 매우 커질 때 최고차항 외의 것을 제외함으로써 시간 분석을 간단하게 하는 것에 의미가 있다.
무한히 큰 입력값이 들어 왔을때, 상수와 다른 항의 값은 큰 차항에 비해 영향이 미비하기 때문에 접근적 표기법을 사용해 표기하는 것이다.