알고리즘_시간복잡도, 공간복잡도, Big-O 표기법

안녕하세요. 문범우입니다.

최근 Java로 알고리즘 스터디를 시작하게 되었습니다.

단순히 문제풀이 보다는 이론적인 내용들을 살펴보며 관련된 문제를 푸는 방식으로, 기초부터 다시 살펴보려합니다.

이번에는 직접적인 알고리즘 내용에 앞서, 알고리즘 분석 즉 시간복잡도와 공간복잡도에 대해 이야기를 먼저 진행해보겠습니다.

---

> 왜 알아야 하는가?

Big-O 표기법은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다.

이를 통해 자신이 작성한 알고리즘이 이전보다 빨라졌는지 느려졌는지 판단하는데 도움이 될 것이다.

물론 이 외에 다른 개발자들과 특정 알고리즘에 대해 이야기하거나 효율성 판단등에 의해서 Big-O 표기법을 통해 보다 원활하게 의사소통을 진행할 수 있다.

실제로 Big-O 표기법 이외에 다른 표기법도 있으나 이에 대해서는 혼동을 피하기 위해 제일 마지막에서 언급하겠다.

또한 Big-O 표기법에 대해 이해하는 방식이 조금씩 상이할 수 있지만 그 정의를 정확하게 이해한다면 문제되지 않을 것이다.

> Big-O 표기법의 정의

Big-O 표기법은 사전적으로, 시간(또는 공간)의 상한을 이야기한다.

즉, 시간복잡도와 공간복잡도의 상한에 대해서 이야기하는 것이다.

(주로 시간복잡도를 다루게 될 것이므로 시간을 대표로 설명하겠다.)

정의대로 이야기한다면 시간복잡도에 대해서 이야기할 어떤 것의 최악의 경우(가장 느렸을 경우)에 대한 시간을 이야기 하는 것이다.

즉, 평균적으로 10시간이 걸리는 업무가 있지만 특정 상황에 따라 20시간이 걸린다고 생각해보자. 이때 그 업무에 대한 시간의 상한은 20시간이다. 아무리 오래 걸려도 20시간이면 되기때문이다.

이때 이야기 하는 '아무리 오래 걸려도' 라는 키워드가 결국 Big-O이다.

그럼 이러한 의문이 들 수 있다.

"그럼 그 업무는 아무리 오래 걸려도 100시간 안에 할 수 있으니, 시간의 상한이 100시간이라고 해도 맞는건가요?"

그렇다. 정의에 따라서는 전혀 틀린말이 아니고 수학적으로도 옳은 표기이다.

하지만, 대체로는 그렇게 이야기하지 않는다.

Big-O가 대략적으로 어떤걸 의미하고자 하는지 이해가 갔다면 조금 더 수식적으로 살펴보자.

이를 위해서 위에서 언급한 예시를 조금 더 구체화 해보자.

특정 업무에 대해서 처리할 문서가 n개라고 가정하자.

이때 만약 A라는 사람은 정직하게 일해서 문서당 소요시간이 1시간이다.

근데 B라는 사람은 아직 경력이 부족해서 문서당 소요시간이 2시간이다.

슬프게도 C라는 사람은 호기심이 많아 문서개수에 대해 제곱시간이 소요된다.

놀랍게도 D라는 사람은 자동화 툴을 만들어 놓아서 문서개수에 상관없이 10시간이 소요된다.

이러한 사람들에 대해 각각 Big-O로 소요시간을 나타내보자.

A는 O(N)이다.

문서 1개당 소요시간이 1시간이므로 문서가 늘어나면 소요시간도 선형적으로 늘어난다.

B는 O(2N)이다.

A와 비슷하게 선형적으로 늘어나지만 그 값이 2배일 뿐이다.

C는 O(N^2)이다.

A와 B에 비해 호기심이 많은 C는 문서당 제곱시간이 소요된다고 하였기에 위와 같이 표기된다.

D는 O(10)이다.

자동화 툴을 만들어 놓은 D는 문서 개수와 상관없이 무조건 10시간이 소요된다.

Big-O표기는 위와 같이 표기하는 것이다.

하지만 아직 한가지가 남았다. Big-O 에서는 작은 것들은 신경쓰지 않는다.

정말 간단하게 이야기한다면 Big-O 표기법은, 제일 영향력있는 놈만 신경쓰겠다는 이야기다.

실제로 알고리즘에 큰 영향을 주는 것만 고려하겠다는 이야기인 것이다.

이것은 특정 수식에서 최고차항을 제외한 나머지를 무시한다는 의미이기도 하며, 최고차항에 대한 상수배 또한 무시하겠다는 것이다.

최고차항에 대한 상수배를 무시하겠다는 것은

즉, Big-O 정의에 따르면, O(N)과 O(2N)은 모두 동일하게 O(N)으로 표기된다.

그렇다면, O(10)은 어떻게 표기될까?

상수 시간이므로 O(1) 로 표기된다.

그리고 최고차항을 제외한 나머지를 무시하겠다는 것은,

O(N^2 + 10N + 3) 으로 표시된 값이 있을때 이를 O(N^2)과 같이 표기하겠다는 것이다.

위와 같이 알아본 Big-O 표기법은 초기에 언급한 것과 같이 단순히 시간복잡도를 분석하는데만 사용되지 않는다. 시간 또는 공간 모두 분석하는데 사용되며 공간에 대해 분석하는 것을 공간복잡도라고 이야기한다.

공간복잡도에 대해서 추가적인 설명을 하자면 다음과 같다.

> 공간복잡도

재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.

하지만 함수를 단지 n번 호출했다고 해서 무조건 O(n) 공간을 사용하는 것은 아니다.

Big-O 표기법에서 주로 사용되는 표현들에 대한 대소비교를 해본다면 다음과 같다.(시간복잡도, 공간복잡도 순서)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

그럼 마지막으로, 처음에 이야기했던 Big-O 이외의 표기법들에 대해 간단히 알아보자.

+ Big-Omega

빅 오메가라고 부르는 표기법은 시간에 대한 등가 또는 하한의 개념을 나타낸다.

즉 모든 process는 Ω(1)로 표기할 수 있다. 결국 오메가로 표기되는 알고리즘은 Ω 수행시간보다 빠를 수 없다.

+ Big theta

빅 세타라고 부르는 표기법은 Big-O와 Big-Omega 모두를 이야기한다.

즉, 특정 알고리즘의 시간복잡도가 O(N) 이면서 Ω(N) 이라면 이는 θ(N)이라고 표기할 수 있다.

---

이렇게 Big-O에 대한 개념적인 내용을 정리해보았습니다.

추후 필요하다고 생각되면 특정 코드나 내용들에 대해 시간복잡도와 공간복잡도를 계산해보는 내용에 대해서도 정리해보겠습니다.