웹 개발자를 위한 자료구조와 알고리즘 ( a.k.a 웹자알 ) 시리즈의 첫 포스팅입니다!
오늘 배울 개념은 Big-o Notation (빅오 표기법) 인데요.
빅오 표기법이란 ?
- 알고리즘의 “효율성”을 평가하기 위한 분석법.
- 시간 복잡도(실행시간)와 공간 복잡도(실행공간)로 이루어진다.
- 이해한다면 앞으로 알고리즘 보는 눈이 번.쩍..!
빅오 표기법은 기본적으로, 알고리즘 최악의 경우 복잡도를 측정합니다.
( ** 위 그래프의 x축을 “ 자료 입력 개수” , y 축을 “ 시간 ” 으로 이해하세요.)
빅오 표기법을 고민할 땐, 이것만 기억하세요.
“n이 무한으로 접근하면 무슨 일이 일어날까?”
대표적인 O(n)에 대해 이야기해봅시다.
이해를 돕기 위해 예를 들겠습니다.
O(n)은 선형 시간이고, 위의 예에서 최악의 경우
i는 0부터 n-1까지 n번의 연산을 수행해야합니다.
이를 이해했다면 다음은 어떤 시간 복잡도를 나타낼까요?
눈치채셨겠죠? 위의 예시는 순서대로 O(n²), O(n³)의 시간복잡도를 가집니다.
로그 시간 복잡도의 효율은 백만 개의 항목 이상의 큰 입력이 있는 경우에 분명합니다. n이 백만이라고 하더라도 log2(1,000,000) = 19.9315…이기 때문에 단지 19개의 항목만을 출력합니다. 이해가 어렵다면 직접 콘솔로 찍어보시길!
여기까지 이해하셨다면..? 빅오 표기법 규칙은 아주아주 쉽게 이해할 수 있습니다 !
혹시 고등학교 시절 수학시간에 배운 “극한”의 개념에 대해서 기억하시나요!?
(몰라.. 모른다고..!!!)
(헤헤..) 만약 이해가 어렵다면! 극한의 성질을 이해해보세요! (딱 요정도..?)
(기억나셨죠..?)
알고리즘의 시간 복잡도를 f(n)이라고 표현했을 때, n은 입력 개수를 나타냅니다.
f(n) time : 필요한 시간
f(n) space : 필요한 공간 (추가적인 메모리)
알고리즘의 분석 목표는 f(n)을 계산함으로써, 알고리즘의 효율성을 제대로 이해하는 것입니다. 하지만 f(n)을 계산하는 것은 생각보다(?) 어려울 수 있습니다.
때문에 빅오 표기법 규칙을 참고해야 합니다!
- 계수 법칙 :
상수 k>0인 경우 f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다.
예시로 한 번에 이해합시다!
위 예시에서 Case 1의 시간복잡도는 f(n)=n, Case2의 시간복잡도는 5f(n)입니다.
( for문이 각각 0에서 n까지, 0에서 5n까지 실행되기 때문입니다.)
하지만 n이 무한대로 커진다면..? 또는 아주 큰 수에 가까워진다면? 계수가 존재한다고 해서 달라지는 것은 없습니다. 따라서 이를 무시합니다.
즉, Case 1과 Case 2의 시간복잡도는 O(n)으로 동일합니다.
- 합의 법칙 :
f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면 f(n) + g(n)은 O(h(n)+p(n))이다.
바로 예시를 들어보겠습니다!
위의 예에서 4번째 줄 (for문 안에 있는 block)은 f(n)=n에 해당하고, 일곱 번째 줄은 f(n)=5n에 해당합니다. 이로 인해 결과값은 n+5n = 6n입니다.
6n..? 뭐 kn..? 그렇다면 .. 계수 법칙..? (답 아시겠죠..?)
최종결과는 O(n) = n이다!
- 곱의 법칙 :
f(n)이 O(h(n))이고 g(n)이 O(p(n))이면 f(n)g(n)은 O(h(n)p(n))이다.
시간을 거슬러.. 아까 처음에 빅오의 법칙을 소개하며 이중 for문 과 삼중 for문을 비교했던 걸 기억하시나요..?
(대충 O(n²), O(n³)을.. 기억하라는 글…)
바로 예시로 이해합시다!
위의 예에서 f(n)= 5n * n 입니다. 여섯 번째 줄이 내부 loop에 의해 5n번 실행되고 내부 loop는 외부 loop에 의해 (네 번째 줄) n번 실행되기 때문입니다.
따라서 결과는 5n²번 연산이 일어납니다.
이번에도 계수 법칙을 적용하면 O(n) = n² 이 됩니다.
- 전이 법칙 :
f(n)이 O(g(n))이고 g(n)이 O(h(n))이면 f(n)은 O(h(n))이다. 이건 너무 쉽죠..?
- 다항 법칙 :
f(n)이 3(k)차 다항식이면 f(n)은 O(n³(k))이다.
다항법칙의 예시를 살펴보자.
f(n)이 2차 다항식이기 때문에 (네 번째 줄이 n*n회 실행되기 때문)
O(n) = n² 이 됩니다.
지금까지 빅오 표기법에 대하여 설명했습니다.
생소하다면 생소하겠지만 알고리즘의 효율성을 파악하기 위해선
반드시 이해해야만 하는 개념입니다.
정리
- 빅오는 알고리즘의 효율을 분석하고 비교하는 데 매우 중요하다.
- 우선 빅오를 분석하기 위해서는 코드를 살펴보고, 빅오 표기법을 단순화하고자 다음 법칙들을 적용해야 한다. 다음은 가장 자주 사용되는 법칙들이다.
- 계수/상수 제거하기 (계수법칙)
- 빅오 더하기 (합의 법칙)
- 빅오 곱하기 (곱의 법칙)
- 빅오 표기법의 다항 결정하기 (다항 법칙)
f(n) space 공간 복잡도의 경우,
해시 테이블이나 배열에 대한 개념을 충분히 다루고 나서 언급하도록 하겠습니다.
질문은 언제나 환영입니다. 환절기 감기 조심하세요 :)
