알고리즘 테스트를 보게 되면 시간복잡도를 낮추라는 요구 사항을 마주하게 된다.

시간복잡도라는 단어 자체가 이 개념에 대해서 더 어렵게 만드는 것 같다.

알고리즘의 시간복잡도는 단순히 알고리즘 즉 어떤 문제를 해결하는 프로그램의 실행 속도를 객관적으로 나타내는 수치에 불과하다.

시간복잡도라는 단어의 어감때문에 눈치채지 못했지만 시간복잡도는 반복문에 의해서 좌지우지된다.

그러니까 얼마나 반복 회수를 줄이냐의 문제인 것이다.

다음과 같이 출근하는 과정을 알고리즘적 사고로 풀어본다면

출근하는 과정
1. 세면세족
2. 환복
3. 지하철역으로 이동
4. 지옥철 탑승 (1시간 이동)
5. 지옥철 하차
6. 사무실 입성

4번의 지하철 탑승 시간이 출근 시간의 대부분을 차지하기 때문에 지하철 탑승 시간을 줄인다면 출근 시간에 대한 문제를 효율적으로 관리 할 수 있을 것이다.

프로그래밍에서의 알고리즘 시간복잡도를 해결하는 방법도 앞서 살펴본 현실의 예제와 크게 다르지 않다.

알고리즘 성능 표기법

알고리즘의 시간복잡도를 나타낼 때, 빅오 표기법이라는 것을 사용한다.

Big O 표기법은 O(1), O(logN), O(N), O(nlogN), O(N^2), O(2^N), O(N!)로 표현한다.

• 최대 2회(상수회) 실행한다: O(1)

if n > 10: # n이 1일 경우, 10과 n을 비교하는 조건문을 실행
  print(n) # 조건문에 만족하면 print 함수를 실행

• n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)

variable = 1 # 변수 할당에 1회 실행
for num in range(3): # 안쪽 반복문을 3회 반복 실행
  for index in range(n): # n번 반복 실행
    print(index) # 반복문 당 1회씩 실행

• n에 따라, $n^2$번, $n^2$ + 1000 번, 100$n^2$ - 100, 또는 300$n^2$ + 1번등 실행한다: O($n^2$)

variable = 1 # 변수 할당에 1회 실행
for i in range(300): # 안쪽 반복문을 300번 반복 실행
  for num in range(n): # 안쪽 반복문을 n번 반복 실행
    for index in range(n): # n번 반복 실행
      print(index) # 반복문 당 1회씩 실행

시간복잡도를 적용한 알고리즘

잠시 학창 시절의 수학 시간의 기억을 되짚어 보면 1부터 n까지의 합을 구하는 공식이 있었다.

이를 프로그래밍으로 구현하면 다음과 같이 구현할 수 있다.

def sum(n):
  total = 0
  for num in range(1, n + 1):
    total += num
    return total
    
sum(100) # 5050

이렇게 구현된 1부터 n까지의 총합을 구하는 함수의 시간복잡도를 계산해보면 반복문을 n번 반복하기 때문에 O(N)이 나온다.

이 함수의 시간복잡도를 줄일 수 없을까? 정답은 수학시간에 배웠던 공식을 떠올리면 된다.

이 문제에서는 해당 수학 공식이 이 문제의 시간 복잡도를 효율적으로 관리할 수 있는 알고리즘인 것이다.

공식은 n번 째 항에 n+1번 째 항을 곱한 값을 2로 나누는 것이다.

n(n+1) / 2

def sum(n):
  return int(n * (n + 1) / 2)
  
sum(100) #5050

앞서 작성한 코드의 시간복잡도는 O(N)이지만 수학 공식을 적용한 sum함수의 시간복잡도는 O(1)이다.

이처럼 알고리즘의 시간복잡도를 줄이는 것은 프로그램의 성능을 높일 수 있는 방법 중 하나이므로 어렵다고 학습하기를 나중으로 미루지 않아야 할 개념이다.