Big-O에 대해 어렴풋이 알고 있지만, 이번 기회에 복습 겸 간단하게 작성해봅니다.
"Big-O는 알고리즘과 관련이 있는데, 알고리즘은 무엇인지 설명하라고 하면 어떻게 말해야하지?"
보통 알고리즘이 무엇인지는 물어보지 않지만, 알고리즘이 무엇인지 알면 Big-O는 무엇이고 왜 사용하는지 자연스럽게 이해가 된다고 생각합니다.
쉽게 이해될 수 있도록, 공부하면서 메모해보았습니다.
알고리즘이란?
알고리즘이 무엇인가 생각해 보면 leetcode나 codewars 혹은 백준 알고리즘 문제들이 떠오릅니다.
알고리즘은 그럼 그 문제들에 해당되는 건가? 이 부분이 항상 애매했었는데요.
정의를 찾아보니 알고리즘은 문제를 해결하기 위한 절차나 방법이다. (1)라고 합니다.
그러니까 본래 알고리즘을 연상했을 때 떠올렸던 문제들은 알고리즘 "문제"들이고, 그 문제들을 풀기 위해 작성했던 일련의 연산 로직이 알고리즘이라는 것이네요.
이제서야 알고리즘 문제와 알고리즘을 구분할 수 있게 된 것 같습니다.
조금 더 찾아보니, 알고리즘은 만족해야 하는 다섯가지 조건이 있다는데요. 가볍게 하나씩 보겠습니다.
- 입력
알고리즘은 외부에서 제공된 0개 이상의 자료가 존재한다. 따라서 알고리즘에는 입력이 있을 수도 있고 없을 수도 있다. - 출력
알고리즘은 결과를 가져야 한다. 갯수는 1개가 될 수도 있고 그 이상이 될 수도 있다. - 명확성
알고리즘의 각 단계는 명확하여 애매함이 없어야한다. 이 조건에 따라 난수를 사용하는 절차는 알고리즘에 포함되지 않을 것 같지만, 난수의 확률 분포가 가져야하는 특성이 명백하다면 알고리즘에 포함한다. - 유한성
알고리즘은 유한한 횟수의 단계로 문제를 해결하고 종료해야한다. 즉 알고리즘은 각 단계를 거칠 때마다 나머지 실행 단계의 횟수가 줄어들어야한다. - 효과성
알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.
(1)
알고리즘은 문제를 해결하는 절차나 방법을 가리킨다.
알고리즘은 만족해야하는 조건이 5가지가 있다.
위의 5가지 조건을 만족하면 문제를 해결할 수 있는 알고리즘입니다.
그렇다고 알고리즘이 "효과적으로" 문제를 풀어낸다고 할 수는 없습니다.
같은 문제를 유한한 시간내에 풀더라도, 어떤 알고리즘은 몇 달에서 몇 년이 걸릴 수도 있고, 다른 알고리즘은 몇 초 만에 해결할 수도 있기 때문입니다.
그리고 시간이란 자원은 한정되어 있기 때문에, 저희는 같은 알고리즘이더라도 좀 더 문제를 "효과적"으로 풀어낼 수 있는 알고리즘에 관심이 있는 것이죠.
그러면 알고리즘은 어떻게 효과적인지 판단할 수 있을까요?
각 알고리즘마다 문제를 푸는데 걸리는 시간을 잰다면 어떨까요?
물론 이 방법도 있겠지만 알고리즘이 얼마나 걸릴지도 모르고, 수 많은 알고리즘을 일일이 시간을 잰다는 것은 여간 번거로운 일이 아닐 것 입니다.
그래서 알고리즘의 효율성을 평가하고 나타내기 사용하는 것이 Big-O 표기법입니다.
Big-O
비유
알고리즘과 Big-O는 잠시 뒤로하고, 다른 지역에 살고 있는 친구에게 파일을 가능한한 빨리 전해야하는 상황에 있다고 가정해봅시다.
인터넷을 통해 전송하면 되겠다고 생각할 수 있지만, 이 방법은 파일 용량에 따라 가장 빠른 방법이 될 수도 있고, 가장 느린 방법이 될 수도 있습니다.
물론 파일의 용량이 작으면 인터넷으로 빠른시간내에 전송할 수 있습니다.
만약 파일 용량이 엄청나게 크다면 어떨까요? 어쩌면 택배로 파일이 들어있는 USB나 외장하드를 보내는 것이 더 빠를 수도 있습니다.
시간 복잡도
이렇게 입력(파일 용량)의 크기가 충분히 클 때에 대해서 수행 시간을 분석하는 것이 점근적 분석 (asymptotic analysis), 또는 Big-O 시간에 대한 개념입니다.
위에서 살펴본 데이터 전송 '알고리즘'의 실행 시간을 다음과 같이 설명할 수 있습니다.
- 온라인 전송: O(s), s는 파일의 크기. 파일의 크기가 증가함에 따라 전송시간 또한 선형으로 증가한다
- 택배를 통한 전송: 파일 크기에 관계 없이 O(1). 파일 크기가 증가함과 관련 없이 전송시간은 항상 일정하다
상수가 얼마나 큰지, 아니면 선형식이 얼마나 천천히 증가하느지에 관계없이 숫자가 커지다 보면 선형식은 언젠가 상수를 뛰어넘게 된다 (2)
O(s) 와 O(1) 외에도 다양한 종류의 실행 시간이 존재합니다. ex) O(log N), O(Nlog N), O(N), O(N^2), O(2^N)
실행 시간에는 다양한 변수가 포함될 수도 있습니다. 예를 들어, 너비가 w이고 높이가 h인 울타리를 색칠하는 데 소요되는 시간은 O(wh)로 표기할 수 있는 것 처럼요.
공간 복잡도
알고리즘의 효율성 평가에는 고려해야할 자원이 시간뿐 아니라 메모리도 있습니다. 알고리즘을 실행하는 컴퓨터 내부의 메모리 또한 한정적이기 때문이죠.
공간 복잡도는 시간 복잡도와 유사한 성질을 띄는 개념입니다. 크기가 n인 배열을 만든다면 O(n)의 공간이 필요하고, n x n 크기의 2차원 배열을 만들고자 하면 O(n^2)의 공간이 필요합니다. (2)
재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함됩니다.
예를 들어 다음 코드는 O(n)의 시간과 O(n)의 공간을 사용합니다.
func sum(n: Int) -> Int {
if (n <= 0) { return 0 }
return n + sum(n - 1)
}sum 함수가 호출될 때마다 스택의 깊이는 깊어지고, 전부 호출 스택에 있으므로 실제 메모리 공간을 차지하고 있다고 볼 수 있습니다.
이번 포스트에서는 알고리즘과 알고리즘의 효율을 나타내는 지표인 Big-O, 그리고 알고리즘의 시간복잡도 공간복잡도 개념에 대해 잠시 살펴보았습니다.
이외에도 Big-O와 관련해서 상수항과 지배적이지 않은 항은 무시하는 것, 상환 시간, log N 수행 시간, 재귀적으로 수행시간 구하기 등의 남은 주제가 있습니다만, 나머지 주제는 추후 포스트에서 다뤄보도록 하겠습니다.
읽어주셔서 감사합니다.
즐거운 하루 되세요 😀
포스트 작성에 참고한 자료:
(1) Wikipedia - Algorithm
(2) Cracking The Coding Interview 6th Edition
