알고리즘 분석 - 시간 복잡도

  이번 시간에는 '알고리즘 분석' 주제로 공부해 보겠습니다. 알고리즘을 왜 배워야 할까요? 코딩은 다했고, 배포도 끝났으며 소스코드에 버그도 없는데 이유 모르게 어플이 느릴때. 이때 코드 최적화를 통해 속도를 높이고 싶을 때 데이터 구조와 알고리즘을 배워야합니다.

Aims

• How do we define a “good” data structure?
• A “good” data structure is fast (efficient) at performing various operations as data grows:
  • Finding stuff
  • Adding stuff
  • Deleting stuff
   
• Operations are algorithms!
• How do we measure the speed (running time) of the operations/algorithms?

Running Time of Algorithms

어떤 문제를 해결하기 위해 알고리즘을 고안할 때, 미리 실행시간(Running time)을 계산해 봐야합니다. 이 실행시간을 계산하는 일반적인 방법이 시간 복잡도를 계산하는 것이고 이를 표기하는 방법이 Big-O 표기법입니다. 

• Algorithms
  • take inputs of varying input sizes n
  • take running time t to perform
• Running time t (usually) grows with the input size n
  • Q: How do we measure t?
  • Q; How fast does t grow as n grows?

Time Complexity (시간 복잡도)

시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됩니다. 즉, 알고리즘을 수행하는데 필요한 연산 횟수! 실제 시간을 측정하는 것이 아니고 ‘얼마나 많은 단계(연산 횟수)가 있는 가’로 측정

The complexity of program/algorithms (time, space, etc.) depends on the problem “size” (input size n). We focus on analyzing the worst-case time complexity

효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같다. 즉, 효율적인 알고리즘을 구현한다는 것은 “입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성”

n = # n에 해당하는 값 지정

# 첫 번째 중첩된 반복문
for i in range(10):
    for j in range(n):
        for k in range(n):
            if True:
                print(k)

# 두 번째 반복문
for i in range(n):
    if True:
        print(i)

 

위 코드의 시간복잡도를 계산하면 다음과 같습니다.

<Big - O 표기법>: 상한 접근, 시간 복잡도를 표기하는 방법

• 시간 복잡도를 표기하는 방법, 일반적으로 최악의 경우에 대하여 나타내는 방법
• 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.
• “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능.
  • 극단적인 예이지만, ‘최악의 경우도 고려하여 대비’ 하는 것이 바람직하다.

빅오 표기법(Big - O notation) 이란 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법입니다. 위 코드에서의 시간 복잡도를 Big-O 표기법을 나타내면 다음과 같습니다.

Big-O 표기법의 예시를 또 들면 다음과 같습니다.

출처: 개발남노씨

컴퓨터는 1초에 2000만 ~ 1억 번 밖에 연산을 못한다.

  보통 시간 복잡도에서의 ‘연산’은 프로그래밍 언어에서 지원하는 사칙 연산, 비교연산, 등과 같은 기본 연산을 의미합니다.. 예를들어, 두 정수 a와 b를 더하는 더하기 연산뿐만 아니라, 두 정수 a와 b의 값을 비교하는 비교 연산 또한 한번의 연산으로 취급합니다. 일반적으로 시간복잡도에 N의 크기를 넣어서 100,000,000(10^8)을 넘으면 시간 초과 가능성이 있다.

문제를 어떻게 풀지 생각하고 코드를 최적화하는 것은 경험의 영역이지만, 문제를 해석하고 어떻게 풀지 전략을 짜는 것은 지식의 영역입니다. 

1. 최대 시간이 1초 일 때, 입력 데이터 수에 따른 시간 복잡도
   • 1,000개라면 -> O(n^2) 이하
   • 10,000개라면 -> O(n^2) 미만(최대한 적게 사용하는 방향으로!)
   • 100,000개라면 -> O(nlogn) 이하
   • 1,000,000개라면 -> O(nlogn) 미안 (가급적 O(n)) 정도로!
2. 자주 사용하는 자료 구조의 시간 복잡도 활용
3. 시간 복잡도 줄이기(파이썬)
   • readline(): 입력 속도 빠르게! sys모듈의 readline()을 활용. 보통 파이썬에서는 데이를 입력받을 때 input() 함수를 사용합니다. 하지만 데이터가 많을 수록 효율이 떨어지기 때문에 readline()를 사용해서 데이터를 빨리 읽어오는 것이 효율적입니다. 
   • 리스트 곱셈: 초기화와 할당 빠르게! 기본적으로 배열(리스트)을 다룰 때는 동적으로 다루지만, 가끔 미리 할당해 놓은 고정 배열에다가 계산해야하는 경우가 있습니다. 이럴 때 리스트에 곱셈 연산을 하여 초기화와 할당을 동시에 진행하도록 만들 수 있습니다.
   • 문자열 합치기: ''.join()을 쓰고 +는 사용하지 말자. 문자열을 합칠 때는 문자열의 개수가 정말 적지않은 이상 + 연산자를 사용하는 것은 좋지 않습니다. 왜냐하면 파의썬의 string은 immutable 하기때문에 + 연산자로 합칠 경우 copy-on-update를 하게 됩니다. 즉, 각각의 문자열을 새로운 메모리에 복사하여 새 문자열을 만들기 때문에 사실상 시간 복잡도가 O(n^2)정도가 됩니다. 따라서 ''.join() 을 사용해 문자열을 합쳐야 이러한 과정을 거치지 않고 빠르게 합칠 수 있습니다.
   • 조건문 연산 줄이기: 짧은 것부터 먼저 계산하자. if 조건문에서 다중 조건을 사용하면 두 조건 중 빨리 실행되는 쪽을 앞쪽으로 배치하는 것이 유리하다. and 연산을 할 때 앞의 연산 결과가 False라면 뒤의 연산은 실행하지 않고 바로 넘어가며, or 또한 앞의 연산 결과가 True라면 뒤의 연산을 실행하지 않습니다.
   • 슬라이싱: 불필요한 연산을 최소로. 리스트, 튜플, 문자열과 같은 자료형에 범위를 지정해 일부분만 추출하는 기능입니다. 슬라이싱으로 하나의 변수를 최대한 활용하는 것 또한 실행 속도를 높이는 데 많은 도움이 됩니다.

*리스트 곱셈

data = [0] * 1000

가장 큰 핵심은 '반복문'

가장 오래 걸리는 반복문을 찾는 것이 핵심입니다. 결국, 가장 오래 걸리는 반복문이 복잡도에 영향을 가장 크게 미치기 때문입니다. 그래서 이 반복문의 시간 복잡도를 구하는 것이 제일 먼저 해야할 일입니다. 다르게 말해, 함수별로 걸리는 시간 복잡도를 예측해 가장 오래 걸리는 함수가 있다면 다른 작업을 줄일지, 아니면 해당 함수를 최적화 할지 전략을 짜는 것입니다. 

크기 N과 M의 시간복잡도 계산

크기가 N과 M인 두 데이터로 연산을 할 때 이를 O(n^2)으로 취급해야 하는지, 아니면 O(n)으로 취급해야 하는지에 대한 문제입니다. 적당하게 O(nm)으로 계산하는 경우도 많지만 정확하게 계산할 수록 유리합니다. 예를들어 다음과 같은 코드가 있다고 해보겠습니다.

for i in N:
	for j in M:
    	...

1. M이 매우 적은 숫자일 경우(~20), M의 연산은 사실상 상수 시간 이내로 끝나기 때문에 조금 연산이 큰 O(n)으로 봐도 무방합니다.
2. M이 어느 정도 큰 숫자일 경우(~100), N X M이 N^2을 넘지 않는다면 N x M으로 계산해야 합니다.
3. M이 N과 거의 비슷하거나 매우 큰 숫자라면 입력 개수의 크기에 비례하는 것과 다름 없으므로 이 시점부터는 O(n^2)으로 취급해야합니다.

O(1)

일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라고 시간이 늘어나지 않는다. 즉, 입력값의 크기와 관계없이 즉시 출력값을 얻을 수 있습니다. 예를들어, 입력과 출력, 간단한 비교 IF문, 곱하기, 배열의 인덱스 참조 등은 상수 시간복잡도를 갖습니다. 

• 입력과 출력: print(), input()
• 곱하기: a[2] *= 2
• 간단한 비교 if문: if(len(a) == 2)
• 배열의 인덱스 참조: a = [1,2,3,4], b = int(a[1])

O(N)

O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것. 예를 들어 입력값이 1일때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있스니다.

O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, O(1) 다음으로 빠른 시간 복잡도를 갖는다. ex) BST의 값 탐색 또한 이와 같은 로직으로, O(log n)의 시간 복잡도를 가진 알고리즘입니다.

O(n^2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다. 

O(2^n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big - O 표기법 중 가장 느린 시간 복잡도를 갖습니다. 구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다. 재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘. 

function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

출처: 개발남노씨

n! > 2 ^ n > n ^2 > nlogn > n > logn > 1 순입니다.