빅 오 표기법(Big-O notation)
- 4 mins빅 오 표기법 (Big-O notation)
알고리즘 공부를 시작할때 제일 처음 나오는 개념이다.
이름만봐서는 당최 무슨 개념인지 감을 잡기 어려웠는데, 공부해보니 그냥 알고리즘의 효율성을 나타내는 지표이다. (그렇다고 마냥 단순하지만은 않음;)
그럼, 알고리즘의 효율성이란 어떤 근거로 판단할 수 있을까?
빅 오 표기법에서는 알고리즘의 효율성을 판단하는 기준으로 크게 두 가지를 사용한다
1. 시간 기준
만약 A, B 두 사람에게 똑같은 일을 시켰는데, A는 한 시간 만에 일을 끝내고 B는 2시간이 걸렸다면, A는 B보다 두 배 정도 효율이 높다고 할 수 있다.
‘사람’이라는 단어는 알고리즘으로 대체하면, A알고리즘이 B알고리즘보다 두 배 정도 효율이 높은 것이다.
하지만 이것은 상대적인 효율성이지, 절대적인 수치로 나타내기엔 애매한 상황이다.
A가 B보다 두 배 빠르다고 해서, “A는 모든 알고리즘에 비해 200%의 효율을 낸다” 라고 할 수는 없으니까.
그리고 컴퓨터 성능에 따라서 같은 상황이라도 더 빠른 시간안에 처리할 수 있으므로 객관성을 부여하기 어렵다.
그래서, 좀 더 합리적인 기준을 위해 시간대신 “처리해야할 데이터에 대한 연산의 횟수” 로 시간 효율성(시간 복잡도)을 계산한다.
그럼 다시,
A에게 1개의 일을 주었다.
A는 한'번'에 일을 마쳤다.
A에게 10개의 일을 주었다.
A는 10'번'에 걸쳐 일을 마쳤다.
...
A에게 N개의 일을 주었다.
A는 N'번'에 걸쳐 일을 마쳤다.
이런 경우는, “A는 N개의 일을 N번 만에 처리한다.” 라고 말할 수 있다.
이를 굳이 Big-O 표기법으로 나타내면 O(N) 이다.
이를 또 굳이 Big-O 표기법으로 표현하면, “알고리즘 A의 시간 복잡도는 O(N) 이다.”
즉, N개의 데이터에 대한 연산 횟수를 기준으로 시간 복잡도를 결정한다.
근데, 이럴수도 있지 않을까?
A에게 N개의 일을 주었다.
A는 N번만에 일을 마쳤다.
A에게 N개의 일을 주었다.
A는 N/2번만에 일을 마쳤다.
A에게 N개의 일을 주었다.
A는 N/3번만에 일을 마쳤다.
N개의 데이터에 대해 항상 N번의 연산을 수행하는 것이 아니라, 어떨때는 그 절반의 연산만을 수행하고, 또 어떨 때는 3배나 빠르게 처리하고있다.
정렬 알고리즘을 예로 들자면, 주어진 데이터가 미리 얼마나 정렬되어있느냐에 따라서 똑같은 알고리즘을 적용해도 연산 횟수의 차이가 생길 수 있다.
데이터를 오름차순으로 정렬할때, [5, 4, 3, 2, 1] 인 리스트를 정렬하는 것과 [1, 2, 3, 4, 5]인 리스트를 정렬하는 경우를 생각해보면 된다.
하지만!
그렇다고해서 어떨때는 시간복잡도가 O(N/2)이 되고 어떨때는 O(N/3)이 되는 것이 아니라, 여전히 시간복잡도는 O(N)이다.
빅 오 표기법에서 시간복잡도는 “최악의 경우” 를 기준으로 산정하기 때문이다.
바꿔 말하면, “이 알고리즘은 어떤 최악의 상황에서도 O(N) 정도의 성능은 낼 수 있다” 라는 것이다.
소프트웨어적 관점에서 봤을때에도, 어떤 소프트웨어가 “평균적으로 얼마정도 성능 이다” 라고 말하는 것 보다는, “절대로 이 것 보다 성능이 떨어지지는 않는다” 라고 말하는 것이 더 신뢰가있다.
소프트웨어가 서비스되는 환경에 따라 평균이라는 기준은 그다지 신뢰하지 못하는 정보가 될 확률이 높기 때문이다.
또한, N + 1의 시간이 걸리는 알고리즘과 3N + 10000의 시간이 걸리는 알고리즘도 둘 다 시간복잡도는 O(N)이다.
이는 점근적 표기법 에 의거, N이 무한히 커진다고 가정했을때, 3이나 10000같은 상수항이 있어봤자 결국에는 최고차항인 N에 비례하는 시간이 걸리기 때문이다.
점근적 표기법
말나온 김에 설명하자면(내가 헷갈리기도 하고), “점근적”이라는 표현은 “점점 근접한다” 정도의 의미로 이해하면 되고, 학창시절 limit의 개념을 공부하며 얼핏 들었던 것 같다.
- N개의 데이터에 대해 N2 + 2N + 1 의 시간이 걸리는 알고리즘이 있다.
- 여기서 최고차항인 N2 과, 나머지 항목인 2N + 1 을 분리해서 생각해보자.
- N의 크기가 계속해서 커진다고 했을때, N2 이 2N + 1 보다 커지게되는 교차점이 생긴다. (N이 3일때, N2은 9가되고 2N + 1은 7이 된다 )
- 그리고, 그 교차점을 지난 이후로는 N이 커질수록 그 차이가 기하급수적으로 벌어지게 된다.
- N이 무한히 커진다고 가정했을때, 사실상 N2 의 값은 N + 1을 무시해도 될 정도로 어마어마하게 그 차이가 벌어지게 될 것이다.
- 따라서 N이 무한정으로 커진다고 가정했을 때, N2 + 2N + 1 의 크기 증가율은 N2 에 비례한다고 해도 무리가 없다.
조금 이상한 비유가 될 수도 있지만, 지구의 부피를 잴 때 굳이 사람이나 동식물, 산과 건물 등 디테일한 오브젝트의 부피를 일일이 전부 재지 않고, 대략적으로 맨틀의 부피 정도만 잰다고 가정해보자.
만약 맨틀의 크기가 계속 커지고, 건물과 사람이 계속 늘어난다고 해도, “지구 부피의 증가율은 맨틀의 부피 증가율에 비례한다” 라고 퉁쳐도 무리가 없을것이다.
빅 오 표기법으로 지구 부피 계산식을 표기하면 O(맨틀부피 + 사람부피 + 건물부피)가 아니라, O(맨틀부피) 이라는 것이다.
마치, O(N2 + 2N + 1) 를 O(N2) 으로 퉁치는 것 처럼.
이상한 비유가 된 것 같긴 한데, 어쨌든 입력의 크기가 아주 클 때, 알고리즘의 성능은 결국 최고차항과 비례하는 수준에서 결정될 것이다.
즉, 입력 데이터 N에 대하여 N2 + 2N + 1 실행 시간을 가지는 알고리즘이 있다고 가정했을때, 이를 빅 오 표기법으로 나타내면 점근적 표기법에 의거해 O(N2)이 되는 것이다.
2. 공간 기준
사실 아직까지 시간 복잡도에 비해 많이 사용되지 않는 것 같지만(=내가 잘 모르지만), 데이터의 양이 기하급수적으로 증가하고있는 4차 산업혁명 시대에서는 점점 중요한 개념이 될 것 같다.
각설하고, 알고리즘이 사용하는 공간을 기준으로 알고리즘의 효율을 따지는 것을 공간 복잡도 라고 한다.
이 때, 알고리즘이 사용하는 공간이란 메모리를 의미한다.
개인적으로 공간 복잡도는 비유를 하는 것 보다는 직접 보는것이 이해가 쉬웠다.
def func(num, n):
result = 0
for _ in range(n):
result += num
return result
num을 n번 더하는 함수이다. 사용하는 변수를 보면 num, range(n), result가 있다.
- num을 위한 공간 1 필요
- range(n)은 크기가 n인 list를 할당하므로, n 개의 공간 필요
- result를 위한 공간 1 필요
즉, 총 n + 2의 공간이 필요하며, 빅 오 표기법으로 나타내면 O(n) 의 공간이 필요하다.
[FUTURE WORK] 공간복잡도에 대한 더욱 깊은 이해가 선행된 이후, 예제 및 활용 범위 추가
코딩장이
-장이: [접사] ‘그것과 관련된 기술을 가진 사람’의 뜻을 더하는 접미사.