[알고리즘] 시간 복잡도, 공간 복잡도, 빅오(Big O)

Big O

빅-오 표기법은 시간복잡도를 표현한는데 사용되며, 계수와 낮은 차수의 항을 제외시킨다. 예를 들어, 만약 크기 n의 입력에 대해 5n3 + 3n의 식을 가진다. 이 알고리즘의 점근적 시간 복잡도는 O(n3)이다.

크기 n의 입력에 대한 복잡도.

• O(1): Constant Time(상수 시간): 작업 수행을 위한 알고리즘은 단일 단계이다.
• O(log n): Logartirhmic time(Log 시간): 작업을 수행하는데 걸리는 단계가 시간이 지날 수록 (어떤 요인에 의해) 점차 줄어든다.
• O(n): Linear Time(선형 시간): 필요한 단계의 수는 직접적으로 관련이 있다. (1 대 1의 관계)
• O(n²): Quadratic Time(이차 시간): 작업을 수행하는데 걸리는 단계의 수가 n의 제곱이다.
• O(C^n): Exponential Time(지수 시간): 작업을 수행하는데 걸리는 단계의 수가 n의 크기에 따라 일정하다. (상당히 큰 수)

O(big-O)

학계에서 big-O는 시간의 상한을 의미한다. 입력 n에 대하여 알고리즘은 O(n)으로 표현할 수 있지만 n보다 큰 big-O 시간을 표현할 수 있다. O(n^2), O(n^3), O(2^n). 즉, 알고리즘 수행 시간은 표현식보다 빠르면 된다. (수행 시간 <= big-O)

Ω(big-Omega)

Ω는 등가 개념 혹은 하한을 의미한다. 입력 n에 대하여 알고리즘 수행 시간을 Ω(n), Ω(log n), Ω(1)로 표현할 수 있지만 해당 표현식 보다 빠를 수 없다. (수행 시간 > big-Omega)

θ(big-theta)

θ는 O와 Ω를 둘 다 의미한다. 즉, 어떤 알고리즘의 수행 시간이 O(n), Ω(n)이라면 θ(n)로 표현할 수 있다.

업계에서는 θ와 O를 하나로 합쳐 표현을 한다. 업계에서 big-O의 의미는 학계에서 θ의 의미와 가깝다.

시간복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

만약 디스크에 있는 파일을 다른 지역에 넘겨주려 할 때 보통은 이메일, FTP, 다른 온라인을 통한 전송 방식을 생각하곤 한다. 이 경우는 대부분 맞을 것이다. 하지만 파일의 크기가 커질 수록 해당 파일을 전송하기 위한 시간은 점차 늘어나게 된다. (시간 복잡도 증가) 예를 들어 1TB 크기 이상의 파일을 전송하고자 한다면 하루가 넘게 걸릴 수도 있다. O(s)
하지만 비행기를 타고 직접 가서 전달한다고 생각해 보자. 파일의 크기에 상관없이 동일한 시간이 걸릴 것이다. O(1)
"위 예제는 코딩 인터뷰 완전 분석을 참고했습니다."

• 온라인 전송: O(s), 여기서 s는 파일의 크기이다. 파일의 크기가 증가함에 따라 전송 시간이 증가한다.
• 비행기를 통한 전송: O(1). 파일의 크기에 관계없이 동일한 시간이 걸린다. 즉, 상수 시간만큼 소요된다.

공간복잡도

알고리즘을 수행하는데 있어서 필요한 메모리(혹은 공간)의 사용량

공간 복잡도의 계산 방식은 알고리즘을 수행하는데 필요한 메모리가 얼마인지를 계산하면 된다. 예를 들어, 입력 n에 대하여 배열 n x n을 만드는 알고리즘이 있다면 해당 알고리즘의 공간 복잡도는 n²이다.

공간 복잡도는 시간 복잡도에 비해 잘 생각하지 않지만 빅 데이터를 처리할 때 문제가 생길 수 있다. 공간 복잡도가 큰 경우 해당 프로그램이 메모리에 한 번에 올라가지 못하여 프로그램이 실행되지 않는 이슈가 생길 수 있다.

. . .

출처

• Algorithms in plain English: time complexity and Big-O notaion
• 시간 복잡도, 위키백과
• 코딩 인터뷰 완전분석
• 시간 복잡도 vs 공간 복잡도, 견우와 직녀