[Algorithm] 계산복잡도

계산 복잡도

오늘은 알고리즘의 복잡도에 대하여 알아보겠습니다.

알고리즘을 공부하는 이유는 좀더 빠르고 효율적이게 하기 위함입니다. 이번시간에는 저희가 짠 코드가 얼마만큼의 복잡도를 가지고 있는지 빅 오 개념을 배워보도록 하겠습니다.

간단한 예제를 보도록 하겠습니다. 1부터 n까지의 합을 구하는 코드를 for 문을 이용하여 구해보도록 하겠습니다.

s = 0
for i in range(1, n+1):
  s += i

print(s)

s는 n번 반복하여 1부터 n까지의 합을 구할 수 있습니다. n이 커질수록 점점 계산의 복잡도가 커지게 됩니다. 이떄 알고리즘의 계산 복잡도를 O(n)이라고 표현합니다. 만약 1부터 2n 까지의 합을 구한다면 복잡도는 O(2n) 만큼으로 증가하게됩니다.

하지만 조금이상하죠?? 저희는 고등교육에서 수열의 합이라는 것을 통해 반복하지 않아도 1부터 n까지의 수를 간단한 공식을 통하여 구할수 있었습니다. 바로 n(n+1) / 2 를 통해서 바로 값을 구할 수 있었습니다. 이때의 계산복잡도는 O(1)입니다. n의 크기와 상관없이 덧셈, 곱셈, 나눗셈으로 한번에 표현할 수 있기때문에 O(3)이 아닌 O(1)로 표현하는 것입니다. 이렇게 최적화된 알고리즘을 사용하거나 수학을 이용하면 좀더 효율적으로 프로그래밍을 할 수 있습니다.