Dazzling 개발 노트
[코드트리] 시간복잡도 본문
기본 연산
강제로 여러 줄의 코드를 한 줄로 몰지 않는 이상, 한 줄에는 하나의 명령이 올 것 입니다.
가장 간단한 연산은 역시 대입일 것입니다.
set a = 10
실제로 a라는 변수를 만들고, 10이라는 값을 할당하는 과정에서 컴퓨터는 많은 연산을 하지만, 우리는 단순하게 O(1)의 연산을 수행했다고 볼 것입니다.
조건문도 비슷합니다.
set a = 5
if a != 10
print('hello')print 같은 메서드를 O(1)이라고 가정한다면, 대입도 O(1)이고 print도 O(1)이니 if a != 10 만 정확하게 알면 될 것 입니다.
그러나 결국 단순히 두 값을 비교하는 연산을 수행하기 때문에, 결과적으로 조건문도 O(1)의 시간복잡도를 보여주게 됩니다.
따라서 위 코드의 시간복잡도는 O(1)이라고 할 수 있을 것 입니다.
이처럼 우리는 앞으로 표기법을 이용해 시간복잡도를 표현하게 될 것입니다.
그렇다면 시간복잡도는 어디에 쓰일 수 있을까요?
보통 for loop을 1억번 도는 데 걸리는 시간이 1초 정도 됩니다. 이를 이용하면 다음과 같은 사실을 알 수 있습니다.
제한시간이 1초인 경우에 대해 떠올린 솔루션의 시간복잡도를 로 계산했다고 생각해봅시다. 그러면 N의 범위에 따라 제한 시간 안에 올바른 답이 나오는 솔루션인지를 빠르게 파악할 수 있습니다.
- , ,
- ,
- , , ,
따라서 제한시간과 솔루션의 시간복잡도를 비교해보고, 만약 시간안에 나오지 않는다면 다른 솔루션을 떠올려봐야만 합니다.
O, Ω, θ 세 구분 기호가 있지만, 실제로는 O만 사용하는 이유?
점근 표기법에는 O, Ω, θ 이라는 세가지 표기법이 있습니다. 만약 시간복잡도 측정 과정에서 Ω을 사용한다면
매우 정확하겠지만, 현실적으로 특정 코드의 시간복잡도를 완벽하게 알기 힘든 경우도 있으므로, 사용을 피하는 편입니다.
또한, θ을 사용하게 된다면 오래 걸리는 코드의 시간복잡도를 너무 낮게 표현할 수 있는 위험이 있으므로,
사용하지 않습니다.
대입과 조건문
function solution()
set data = [] * 3
set data[0] = 12
set data[1] = 15
if data[0] < data[1]
data[2] = 20function solution()
set x = 0
set y = 0
set z = []
if x == y
print(z)
시간복잡도에 대한 옳은 것을 판단해봅시다.
반복문에서의 시간복잡도
앞에서 기본 연산들을 기반으로 시간복잡도를 계산할 땐 상관 없겠지만, while 문이 코드에 들어온다면 시간복잡도는 조금 복잡해 질 것 입니다. 반복문을 언제 빠져나올 지 확실하지 않기 때문입니다!
다음과 같은 코드를 봅시다.
function example(n)
while 0 > n or n > 100
if n < 0
n++
else
n--
return n
이런 코드의 경우 n에 값에 따라 연산의 횟수가 달라질 수 밖에 없으므로, 생각하기 어려울 것 입니다.
사실, 시간복잡도는 일반적으로 최악을 기준으로 계산합니다. 우리가 시간복잡도를 계산하는 이유가 프로그램의 성능을 체크하기 위함이었죠? 당연히 입력값이 아주 크거나 시간이 오래 걸리는 데이터도 들어올 가능성이 존재하므로 최악의 경우를 고려하면 어떠한 상황에서도 프로그램의 성능이 뛰어난지 확인할 수 있을 것입니다.
이 점을 상기한 채로, 반복문의 시간복잡도에 대해 알아봅시다.
for
다음과 같은 코드가 있다고 해 봅시다.
set x = 0
for i = 0 ... i < 10
x += 1
print(x)
for문에 의하여 반복문 내부는 10번 반복됩니다. 여러분들은 이미 내부의 코드의 시간복잡도가 이라는 것을 알기 때문에, 10번 반복을 해도 결국 시간복잡도는 이 될 것 입니다.
그러나 위에서 소개한 코드 처럼 불분명한 값이 들어오게 되면 상황은 달라집니다.
function example(n)
set x = 0
for i = 0 ... i < n
x += 1
print(x)
조금 당황스러울 수도 있지만, 하던 대로 해봅시다. 당연히 for문 내부의 코드의 시간복잡도는 이니, N번 반복을 수행하게 된다면 이 될 것입니다.
N의 값을 판단할 수 없기 때문에, 일반적으로는 N을 그냥 둡니다.
그렇다면 다음 코드는 어떨까요?
set x = 0
for i = 0 ... i < n / 2
x += 1
print(x)
이 코드는 번 수행이 되겠지만, 표기법은 상수를 무시 하기 때문에 마찬가지로 임에 유의합니다.
while
while 문의 경우, 반복문을 탈출할 수 있는 조건이 불분명 하므로 for에 비해 생각해야 할 것이 많습니다.
앞에서 다룬 예제를 다시 가져와보겠습니다.
function example(n)
while 0 > n or n > 100
if n < 0
n++
else
n--
return n
n이 0과 100 사이에 있다면 반복문에 진입 자체를 안 하기 때문에 의 시간이 소요됩니다. 그렇지만 이걸 시간복잡도라고 할 수 있을까요?
n이 만약에 엄청나게 큰 값이라고 합시다. 그렇다면 100 이하가 될 때 까지 계속 내부를 순회해야 하기 때문에, 이론적으로 N - 100회의 순회가 필요할 것 입니다. 따라서 시간복잡도는 자연스럽게 이 될 것 입니다.
이런 부분을 잘 판단하시고 시간복잡도를 하나씩 구해 봅시다.
Side Note
다음 코드의 시간복잡도는 어떻게 될까요?
set x = 0
for i = 0 ... i < n
for j = 5 ... j < n
x += 1
print(x)
for i = 0 ... i < n
x += 1
print(x)
위의 포문은 , 아래 포문은 이지만 N^2이 항상 N보다 크다고 할 수 있기 때문에 해당 코드의 시간복잡도는 이 됩니다.
반복문 내 반복문으로, N번씩 N번 반복한다.
모두 N 반복문을 돈다.
1 - N번 반복
2 - N, M이 주어졌다. N * M번 반복
3 - N, M이 주어졌다. N번 + M번 반복
