[이코테] Chapter1-3 / 복잡도

복잡도

알고리즘의 성능을 나타내는 척도

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

효율적인 알고리즘을 사용한다고 했을 때,
보통 시간 복잡도와 공간 복잡도는 일종의 거래관례(Trad-off)가 성립한다. 

메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 

이때, 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매ㅔ우 큰 경우가 종종 있다.
실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모제이션(Memoization)기법이 있다. 

 

시간복잡도

알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.
코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다.

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다.
엄밀한 정의는 아니지만, 빅오 표기법을 간단히 정의하자면, 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
다시 말해, 함수의 상한만을 나타낸다.

예를들어, N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 생각해보자.
이때 우리는 합계를 저장할 하나의 변수를 선언한 뒤에 모든 데이터를 하나씩 확인하며 그 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있다.

array = [3, 5, 1, 2, 4]		# 5개의 데이터(N = 5)
summary = 0			# 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary += X
   	
# 결과를 출력
print(summary)

15

다음 예제에서는 5개의 데이터를 받아 차례로 5회 더해준다(N = 5)
이때 연산 횟수는 N에 비례하는 것을 알 수 있다. 물론 소스코드에서 summary 변수에 0의 값을 대입하는 연산도 있고, sumary 변수의 값을 출력하는 부분도 있다. 하지만 이런 연산 횟수는 상대적으로 N이 커짐에 따라서 무시할 수 있을 정도로 작아질 것이다. 따라서 본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간 복잡도를 O(N)이라고 표기한다.

몇 가지 예제를 더 살펴보자. 다음 소스코드는 어떤 시간 복잡도를 가질까?

a = 5
b = 7
print(a+b)

a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 이 소스코드의 연산 횟수는 1이다.
단순히 더하기 연산 한 번이 수행되기 때문이다. 이는 상수연산이므로 시간복잡도는 O(1) 로 표현할 수 있다.

다음은 어떤 시간 복잡도를 가질지 생각해보자.

array = [3, 5, 1, 2, 4]		# 5개의 데이터(N = 5)

for i in array:
	for j in array:
    	temp = i * j
        print(temp)

이 소스코드는 데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N^2)의 시간 복잡도를 가진다.
2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문이다.
실은 간단한 2중 반복문이라서 N*N만큼의 연산이 필요하다는 것을 유추할 수 있다

하지만 모든 2중 반복문의 시간 복잡도가 O(N^2)은 아니다. 만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다. 따라서 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다는 점을 기억하자.

반면, 뒤에서(6장)에서 배우게 될 내용 중 하나인 퀵 정렬 평균 시간 복잡도는 O(NlogN) 이지만 최악의 경우 시간 복잡도는 O(N^2)이다. 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다. 그러니 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.

다음은 자주 등장하는 시간 복잡도 표인데, 위쪽에 있을수록 더 빠르다. 
시간 복잡도에 따라서 부르는 명칭이 있는데 예를들어 O(1)는 '상수 시간', O(N)은 '선형 시간' 등으로 부른다.

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O((N^3)	삼차 시간
O(2^n)	지수 시간

 

• 또한, 흔한 케이스는 아니지만 이론적인 계산이 아닌, '실제 코딩 테스트'에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란하다.
  연산 횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘이 있다고 가정하자. 빅오 표기법에서는 차수가 가장 큰 항만 남기기 때문에 O(N^3)표기되지만, 실제로 N이 작을 때는 상수 값인 1,000,000이 미치는 영향력이 매우 크다. 
  예를 들어 N = 10 일 때, 3N^3 + 5N^2 + 1,000,000 = 1,003,500이므로 상수의 영향이 크다. 
  일반적인 코딩 테스트에서는 상수를 고려해야 하는 경우는 적지만, 이처럼 비오 표기법이 항상 절대적인 것은 아니라는 점을 기억하자.
  
  더불어 컴퓨터 과학에서는 특정한 알고리즘의 시간 복잡도가 O(N^K)일 때 (이때 K는 상수값을 가진다), 이를 '다항 시간에 동작하는 알고리즘'이라고 말한다. 

이차 시간, 삼차 시간 등이 모두 다항 시간에 해당한다. 이론적으로는 특정한 문제가 이러한 다항 시간 알고리즘으로 풀 수 있을 때 해당 알고리즘은 풀 만한 알고리즘으로 분류되지만, 실제로는 그렇지 않다.

일반적으로 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다.
왜냐하면 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산횟수가 10억을 넘어가면 C언어를 기준으로 통상 1초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸릴 수 있다. 
특히 파이썬은 더욱 오래 걸리며, 코딩 테스트 문제에서 시간 제한은 1~5초가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정을 받을 수 있다.

각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라서 어떻게 분포되는지 확인해보자.
다음은 대략적인 연산 횟수를 비교한 표로, 시간 복잡도가 동일하더라도 실제 연산 횟수에서는 차이가 날 수 있다.
시간 복잡도가 O(NlogN)인 알고리즘은 매우 다양하다. 빅오 표기법으로 표시한 시간 복잡도가 같더라도 알고리즘 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번, 100,000번 등 실제 수행되는 연산 횟수는 다를 수 있다.

	N이 1,000일 때의 연산 횟수
O(N)	1,000
O(NlogN)	10,000
O(N^2)	1,000,000
O(N^3)	1,000,000,000

※ NOTE - 보통 시간 복잡도에서의 '연산'은 프로그래밍 언어에서 지원하느 사칙연산, 비교 연산 등과 같은 기본 연산을 의미한다. 예를 들어 두 정수 a와 b를 더하는 더하기 연산뿐만 아니라, 두 정수 a와 b의 값을 비교하는 비교 연산 또한 한 번의 연산으로 취급한다.

시간 복잡도 분석은 문제 풀이의 핵심이다.
알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 한다.
문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있기 때문이다. 
예를 들어 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간복잡도로 동작하는 알고리즘을 작성해야 할 것이라고 예상할 수 있다. 혹은 데이터의 크기나 탐색 범위가 100억이나 1,000억을 넘어 가는 경우 이후 장에서 다룰 '이진 탐색'과 같이 O(logN)의 시간복잡도를 갖는 알고리즘을 작성해야 할 것이다.
그래서 실제로 알고리즘 대회 참가에 익숙한 사람들은 문제의 조건을 확인한 뒤에 사용할 수 있는 알고리즘을 좁혀 나가는 전략을 채택하기도 한다.

일반적으로 문제를 풀 때의 예시를 몇 가지 소개하겠다. 
다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000인 경우 : 시간 복잡도가O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

공간 복잡도

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다.
즉, 공간 복잡도 또한 O(NlogN), O(N^2)등으로 표기한다. 다만, 앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다.
일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 쉽게 말해 코딩 테스트 문제에서 보이는 '시간 제한 1초, 메모리 제한 128MB'와 같은 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위하여 명시하는 것이다.

코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. * 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 떄문이다. 
그렇다면 고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자. 단, 실제로 컴퓨터 시스템에서 차지하는 메모리양은 컴파일러에 따라 조금씩 다르게 적용될 수 있다.

• int a[1000] : 4KB
• int a[1000000] : 4KB
• int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다.
다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다는 의미이다.
파이썬에서는 int 자료형이 없지만 , 파이썬에서도 대략 100만개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억하자. 만약 리스트의 크기가 1,000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것이 아닌지 고민해봐야 한다.

시간과 메모리 측정

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 
알고리즘을 공부하는 과정에서 시간을 측정하는 작업을굉장히 많이 사용한다.
실질적으로 알고리즘의 소요 시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있기 때문이다.
다시 말해 실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방벙이다.
특정한 프로그램의 수행 시간을 측정하는 소스코드 예시는 다음과 같다.

[수행 시간 측정 소스코드]

import time
start_time = time.time()			# 측정 시작

# 프로그램 소스코드
edn_time = time.time()				# 측정 종료
print("time :", end_time - start_time)		# 수행 시간 출력

수행 시간 측정 소스코드의 형태는 일반적으로 위와 같다.
보통 어떤 알고리즘을 설계한 뒤에 시간 복잡도를 경험적으로 증명하고 싶을 때는 위와 같은 형태의 코드를 자주 이용한다. 
예를 들어 '선택 정렬'과 '파이썬의 기본 정렬 라이브러리'의 속도를 비교할 때는 다음 쪽과 같이 소스 코드를 작성할 수 있다. 선택 정렬을 사용할 때 최악의 경우 시간 복잡도가 O(N^2)이며, 파이썬의 기본 정렬 라이브러리는 최악의 경우 시간복잡도 O(NlogN)을 보장하여 상대적으로 빠르다. 다음 소스코드의 실행 결과가 그러한 차이를 직접적으로 보여준다.

from random import randint
import time

# 배열에 10,000개의 정소를 삽입
array = []
for _ in range(10000):
    array.append(randint(1, 100))   # 1부터 100 사이의 랜덤한 정수

# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
    min_index = i   # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

end_time = time.time() # 측정 종료
print("선택 정렬 성능 측정", end_time - start_time)    # 수행 시간 출력

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    array.append(randint(1, 100))   # 1부터 100 사이의 랜덤한 정수

# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

end_time = time.time()  # 측정 종료
print("기본 정렬 라이브러리 성능 측정", end_time - start_time)    # 수행 시간 출력

이 소스코드는 당연히 소스코드를 실행하는 컴퓨터의 성능에 따라서 그 결과가 다르게 나올 것이다.

선택 정렬 성능 측정 6.2634007930755615
기본 정렬 라이브러리 성능 측정 0.0

선택 정렬은 6초정도가 걸렸고, 기본 정렬 라이브러리는 1초도 걸리지 않을 만큼의 짧은 시간이 걸렸다.
이처럼 자신이 설계한 알고리즘의 성능을 실제로 확인하기 위해서, 시간 측정 라이브러리를 사용해보는 습관을 기르는 것이 좋다.

앞서 언급했듯이 복잡도란, 특정한 알고리즘이 계산적으로 얼마나 복잡한지를 나타내는 것이다.
동일한 기능을 수행하는 알고리즘이 2개(각각 A와 B) 있을 때, 만약 A 알고리즘이 B보다 시간 복잡도가 더 높다면, A 알고리즘이 실행 시간 측면에서 성능이 더 낮다는 의미이다.

다시 강조하면 코딩 테스트에서 문제를 풀 때는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다. 일반적으로 알고리즘 문제풀이에서의 복잡도는 계산 복잡도를 의미하는 경우가 많으며, '소스코드가 복잡하게 생겼다'와는 다른말로 사용된다는 점을 기억하자.

별다른 언급이 없다면, '복잡도'란 시간 복잡도를 의미한다.

https://github.com/mgkim-developer/Algorithm-interview/blob/main/(Part1)Comparison%20of%20performance%20time.py

GitHub - mgkim-developer/Algorithm-interview: Algorithm interview