[Algorithm] 시간복잡도 Big-O 표기법

시간복잡도(time complexity)

시간복잡도(time complexity)란 가장 널리 사용되는 알고리즘의 수행 시간 기준입니다.

알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다.

기본적인 연산이란 더 이상 쪼갤 수 없는 최소 크기의 연산이라고 생각하시면 됩니다.

예를 들어 다음은 기본적인 연산이라고 볼 수 있습니다.

 

두 부호 있는 32비트 정수의 사칙연산

한 변수에 다른 변수 대입하기

 

가장 깊이 중첩된 반복문의 내부에 있는 기본적 연산들은 더 쪼갤 수 없기 때문에 이것이 시간 복잡도의 대략적인 기준이 됩니다.

 

시간복잡도가 높다

입력의 크기가 증가할 때 알고리즘 수행 시간이 더 빠르게 증가한다는 의미입니다.

 

시간복잡도가 낮다고 언제나 더 빠른것은 아닐 수 있습니다. 입력의 크기가 충분히 작을 때에는 시간 복잡도가 높은 알고리즘이 더 빠를수도 있습니다.

 

예를들어 같은 일을 하는 두개의 알고리즘이  A,B가 있는데 입력의 크기 N에 대해

A는 10240 + 35 logN

B는 2N^2

시간이 걸린다고 합시다.

알고리즘 A는 입력 크기 N이 증가해도 속도가 거의 변하지 않기 때문에 B보다 전체적인 맥락에서는 빠르다고할 수 있지만 N이 충분히 작을 때(N=10)는 B가 더 빠른 속도를 냅니다.

 

알고리즘 수행속도에 영향을 끼치는 것은 입력의 크기만이다?

입력의 크기만이 알고리즘 수행시간을 결정하는 요인은 아닙니다.

입력이 어떤 형태로 구성되어 있는지도 수행시간에 영향을 끼칩니다.

 

예를들어, 배열의 처음부터 순회하면서 원하는 숫자를 찾아 인덱스를 반환하는 알고리즘의 경우 최선의 경우는 배열의 가장 앞에 원하는 숫자가 있는 경우로 수행횟수는 1입니다.

최악의 경우는 배열의 끝에 있어 모든 배열의 원소를 순환해야 하는 경우로 수행횟수는 배열크기 N입니다.

 

O 표기법

시간복잡도를 계산할 때 가장 깊이 중첩된 반복문만을 고려했던 것처럼 전체 수행시간에 큰 영향이 없는 상수 부분은 무시하고 반복문의 반복 수만 고려하는 표기법입니다.

즉, 주어진 함수에서 가장 빠르게 증가하는 항만 표기하고 나머지 항은 생략하는 표기법입니다.

 

예를들어 O표기법은 다음과 같습니다.

반복문 수행횟수	O표기
N	O(N)
2N^2+5N	O(2N^2)
N^2M+NM^2+logM	O(N^2M+NM^2)

O 표기법의 의미

대략적으로 함수의 상한을 나타내는 의미가 있습니다.

N에 대한 함수 f(N)이 주어질 때, f(N) = O(g(N))이라고 쓰는것은 다음과 같은 의미입니다.

이것이 무슨 말이냐!? 하는 분들을 위해 부연설명을 하자면,

f(N) = N^2 + 100N + 1

일 때

O(N^2)이라고 씁니다.

f(N) = O(g(N))이라고 할 때 g(N) = N^2입니다.

 

g(N)은 f(N)보다는 작지만 N이 매우 큰 수라면 큰 차이는 없어집니다.

이 때 적절한 상수 C를 g(N)에 곱해주면 항상 Cg(N)이 f(N)보다 크다는 얘기입니다.

조건을 만족하는

와 상수 C는 임의의 수로 정할 수 있습니다.

예를들어서,

=1000, C=2라고 하면

Cg(N) = 2000000 이고, f(N)보다 훨씬 큽니다. 이 차이는 N이 커질수록 더 벌어집니다.

이렇게 f(N)함수는 아무리 커봤자 Cg(N)이라는 상한이 있다는 것을 알 수 있습니다.

 

 

 

 

 

알고리즘 문제해결 전략1 책을 공부하고 정리한 내용입니다.