8. 점근적 분석 (Asymptotic Analysis): 파이썬 자료구조와 알고리즘

 

점근적 분석 (asymptotic analysis) 은 어떤 알고리즘에 큰 입력 데이터셋을 적용할 때 알고리즘의 제한 동작과 성능을 설명하기 위한 방법이다. 일반 컴퓨터에서 10억개의 숫자 (10^9) 를 정렬한다고 가정해보자. 숫자는 1 바이트라고 가정하고. 컴퓨터의 CPU 클록은 1GHz (초당 약 10^9 번의 연산) 라고 가정하면, 만약 실행 시간이 O(n^2) 인 알고리즘을 사용하여 숫자를 정렬한다면, 최악의 경우 약 10억초 (약 32년) 가 걸릴 것이다. 끔찍하다. 그러나 O(n)인 알고리즘을 사용하면 대략 수 초가 걸릴것이며, O(log n) 또는 O(1)인 알고리즘을 사용한다면 그보다 훨씬 작은 시간 내에 연산을 완료할 수 있을 것이다. 이와 같이 알고리즘의 시간 복잡도는 알고리즘에 있어 매우 중요하다. 사람들이 언제나 더 좋고 더 빠른 알고리즘을 원하는 이유이다.

 

복잡도에 관련된 내용은 다음을 참고하자.

 

https://lgphone.tistory.com/46

시간 복잡도와 공간 복잡도 (Time Complexity and Space Complexity)

 

복잡도 종류

복잡도 종류 (complexity class) 는 계산에 드는 복잡도에 따라 문제들을 분류해놓은 집합을 뜻한다. 이 때 필요한 것은 복잡도 환산 (reduction) 으로, 한 문제를 원래 문제만큼 어렵게 다른 문제로 변환하는 것을 뜻한다.

 

가장 일반적으로 사용되는 환산은 다항 시간 환산 (polynomial-time reduction) 이며, 이는 환산 절차가 다항 시간이 걸린다는 것을 의미한다.

 

P 문제

복잡도에서 P (polynomial time) 는 결정론적 튜링 기계 (deterministic Turing machine) 로 다항 시간 안에 풀 수 있는 판정 문제 (decision problem) 를 모아놓은 복잡도 종류다. 쉽게 풀어 말하자면, 계산의 각 단계에서 단 한 가지 가능성만을 고려할 수 있는 알고리즘으로, 다항 시간 안에 풀 수 있는 문제다. 어떤 문제를 결정론적 문제로 바꿀 수 있다면, 그 결과는 P에 속하게 된다.

 

NP 문제

NP (non-deterministic polynomial time) 는 비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제의 집합이다. P와 구분되는 점은 비결정론적이란 점이다. 각 계산 단계에서 여러 가능성을 동시에 고려할 수 있는 알고리즘으로 다항 시간 안에 풀 수 있다는 뜻이다.

 

어떤 문제가 적어도 NP에 속하는 어떤 문제만큼 어렵다면 (즉 다항 시간 환산으로 판정될 수 있다면) NP-난해 (NP-hard) 라고 한다. 다른 정의로는, 모든 NP 문제가 다항 시간에 어떤 문제로 환산될 수 있다면 그 문제를 NP-난해라고 한다. 예로, 그래프를 통해 최단 경로를 찾는 외판원 문제 (traveling salesperson problem) 는 NP-난해에 속한다.

 

NP-난해 문제 자체는 NP 문제가 아닐 수도 있다. NP 문제이자 NP-난해인 문제를 NP-완전 (NP-complete) 이라고 부른다. NP-완전은 NP 집합에 속하는 판정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제는 다항 시간 내에 NP-완전 문제로 환산할 수 있다.

 

더 쉬운 설명을 보자.

 

NP에 속하는 문제는 그 문제의 대답이 '예'라는 근거가 주어졌을 때, 그것이 옳은 근거임을 다항식 시간에 확인해줄 수 있는 문제다. 반면 P에 속하는 문제는 그 문제의 질문이 주어졌을 때, Yes 또는 No 의 대답을 다항식 시간에 해줄 수 있는 문제다. NP 문제는 대답이 Yes라는 근거가 제시되었을 때, 그 근거가 맞다는 것만 다항식 시간에 확인하면 될 뿐, No의 경우에는 어떻게 하든 상관없다. 그러나 P 문제는 질문 자체에 대해서 다항식 시간에 Yes 또는 No 대답을 해야한다. 질문에 대답을 한다는 것은 일반적으로 '문제를 푼다'는 것과 일치한다.

 

3의 배수를 구하는 질문을 예로 들어보자.

 

문제 1. 양의 정수 X는 3의 배수인가?

 

[변환] X의 각 자리의 수를 단순히 더한 수 Y를 만든다.

 

문제 2. Y는 3의 배수인가?

 

여기서 문제 1의 답은 문제 2의 답과 일치한다.가령 38673 (X) 이 3의 배수인지 판단하고 싶다면, 3+8+6+7+3 = 27 (Y) 이 3의 배수이므로 38673은 3의 배수가 맞다.

 

문제 1을 풀고 싶다면 문제 2로 변환을 해서 문제 2의 답 (Yes or No) 을 문제 1의 답으로 삼으면 된다. 따라서 문제 2를 쉽게 풀 수 있다면 문제 1도 쉽게 풀 수 있다.

 

해결해야 할 문제 B가 어느 정도 어려운지 모른다고 하자. 유명한 난제군인 NP-완전에 속하는 어떤 문제 A를 문제 1의 위치에 놓고 적당히 변환해 문제 B로 바꾸고 문제 B가 문제 2와 같이 문제 1과 대답이 일치한다면 문제 B는 NP-난해 문제, 즉 이 유명한 난제군에 속한다.

 

P = NP ?

P-NP 문제 (P versus NP problem) 는 복잡도 종류 P 와 NP 가 같은지 여부에 대한 컴퓨터 과학 분야의 미해결 문제다. 결정론적 튜링 기계 (P) 에 사용한 프로그램은 비결정론적 튜링 기계 (NP) 에도 적용할 수 있다. 따라서 P는 NP의 부분집합이 된다. 하지만 P와 NP가 같은 집합인지, 아니면 P가 NP의 진부분집합인지 여부는 아직 밝혀지지 않았다.

 

NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에 P-NP 문제가 P=NP가 되고, 반대로 NP-완전 문제 중 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P=/=NP가 된다.

 

https://www.youtube.com/watch?v=QkSW24mUxN8

더 관심이 간다면 이 영상을 보자!

 

재귀 알고리즘

재귀 알고리즘 (recursion algorithm) 의 3가지 법칙은 다음과 같다.

1. 재귀 알고리즘은 베이스 케이스 (base case), 즉 재귀 호출을 유발하지 않는 종료 시나리오가 있어야한다.
2. 재귀 알고리즘은 상태를 변경하고 베이스 케이스로 이동한다.
3. 재귀 알고리즘은 재귀적으로 자신을 호출한다.

모든 재귀 호출에 대해 재귀 함수는 인수, 반환 주소, 지역 변수를 메모리의 스택에 할당한다. 이러한 데이터를 스택에 넣고 (push) 꺼내는 (pop) 데에 시간이 소비된다. 재귀 알고리즘은 최소 O(n)의 공간을 사용한다. 여기서 n은 재귀 호출의 깊이 (depth) 이다.

 

재귀는 계산이 중복되거나 하위 문제가 겹치는 경우 비용이 많이 든다. 어떤 경우에는 스택 오버플로가 발생할 수 있다. 이러한 이유로 하위문제가 겹치는 경우. 반복문을 사용하는 것이 더 좋은 방법이 될 수 있다. 예를 들면 피보나치 수열의 경우 단순히 재귀 함수를 사용하면 지수시간 (O(2^n))이 걸리지만, 반복문을 사용한다면 O(n)이 걸린다.

 

재귀식

재귀 함수의 실행 시간을 설명하는 데에는 재귀식 (recursive relation) 을 사용한다.

 

여기서 a는 재귀 호출 수, g(n)은 재귀적으로 풀어야 할 각 하위 문제의 크기를 나타낸다. f(n)은 함수에서 수행될 모든 나머지 추가 작업이다.

 

다음 표는 잘 알려진 문제들의 재귀식의 예를 보여준다.

 

재귀식	시간복잡도	문제
T(n) = T(n-1) + 1	O(n)	시퀀스 처리
T(n) = T(n-1) + n	O(n^2)	약수 문제 (handshake problem)
T(n) = 2T(n-1) + 1	O(2n)	하노이의 탑
T(n) = T(n/2) + 1	O(log n)	이진 검색
T(n) = T(n/2) + n	O(n)	무작위 선택 (randomized select)
T(n) = 2T(n/2) + 1	O(n)	트리 순회
T(n) = 2T(n/2) + n	O(n log n)	분할정복 방식의 정렬

 

함수에 대한 재귀식을 작성할 떄는 베이스 케이스 (O(1) 이어야 하므로, T(1)=1) 와 일반 케이스 두 방정식을 작성해야 한다. 피보나치를 예로 분석해보자. 피보나치 수열의 단순 재쉬 함수 알고리즘의 시간 복잡도는 지수 시간이 걸린다. 이에 대한 코드는 다음과 같다.

 

def find_fibonacci_seq_rec(n):
    if n < 2:
        return n
    return find_fibonacci_seq_rec(n-1) + find_fibonacci_seq_rec(n-2)

print(find_fibonacci_seq_rec(8))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/8. 점근적 분석/find_fibonacci_seq.py"
21

 

아주 간단한 코드이지만 이를 분석해보자. 먼저 이 경우, g(n) 은 n-2와 n-1이고, a는 2, f(n)은 1이다. 따라서 재귀식은 다음과 같다.

 

그렇다면 다음 단계의 재귀 식들은 다음과 같이 된다.

 

베이스 케이스는 T(1) = 1 이다. 이의 시간복잡도는 O(1)이 되어야 하므로 n-k = 1, 즉 k = n-1이며 (간단히 재귀식이 k와 n에 관한 식으로 변환되었을 때, n-k를 1로 두고, 그에 따른 결과값인 1을 두고 생각해 보면 된다. 베이스 케이스는 T(1)=1 이기 때문이다), 이를 식에 대입해보면,

따라서

시간 복잡도는 위와 같다.

 

시간 복잡도의 계산에 대한 더 자세한 내용은 다음 링크를 참조하자.

http://egloos.zum.com/springmvc/v/563923

점근적 분석 방법, 알고리즘의 시간을 계산하라! - 반복대치

 

위는 피보나치 재귀 함수의 호출 과정을 트리로 나타낸 그림이다.

 

다음 표는 몇몇 알고리즘에 대한 실행 시간 결과다.

 

시간복잡도	실행 시간	알고리즘 예
O(n^2)	2차	삽입 정렬, 선택 정렬
O(n log n)	로그 선형	퀵 정렬, 병합 정렬 등 문제를 작은 덩어리로 분해한 후 그 결과를 병합하는 알고리즘
O(n)	선형	리스트 순회
O(log n)	로그	이진 트리 검색
O(1)	상수	해시 테이블 검색 및 수정
O(n^k)	다항	n번 순회하는 반복문이 k번 중첩
O(k^n)	지수	n개의 모든 부분집합 나열하기
O(n!)	팩토리얼	n개의 모든 순서 나열하기

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인

https://www.youtube.com/watch?v=QkSW24mUxN8

http://egloos.zum.com/springmvc/v/563923