오늘은 알고리즘 효율성 분석에 대해 알아보려고 한다.
* 좋은 알고리즘은?
- 시간효율성 : 이론적분석에 사용, 컴퓨터마다 다르게 측정된다.
- 공간효율성 : 코드효율성(코드 보수성), 알고리즘이 사용하는 메모리 공간
====> 보통 시간 효율성을 더 중요시 한다고 한다.
====> BUT! 이론적인 복잡도 분석 > 절대적인 시간 측정
* 알고리즘 복잡도 분석에서 중요한 점
1. 알고리즘에서 입력의 크기는 무엇인가?
2. 복잡도에 영향을 미치는 가장 핵심적인 기본 연산은 무엇인가?
3. 입력의 크기가 증가함에 따라 처리시간은 어떤 형태로 증가하는가?
4. 입력의 특성에 따라 알고리즘 효율성에는 어떤 차이가 있는가?
1. 입력의 크기
- 알고리즘의 효율성은 입력크기(개수)의 함수형태로 표현
- 무엇이 입력의 크기를 나타내는지를 먼저 명확히 결정
예)
- 리스트 A에서 어떤 값을 찾는 문제 ==> len(A)
- n차 다항식 p(x) ==> n+1
- 가로가 Cx 세로가 R행렬의 연산 ==> C와 R
2. 기본 연산
- 알고리즘에서 가장 중요한 연산
- 이 연산이 실행되는 횟수 만을 계산
3. (복잡도 함수와) 증가속도
* 복잡도 함수
시간복잡도 함수 ====> Ta(n) = 2, Tb(n) = 2n, Tc(n) = 2n^2(n제곱임)
n = 1일때, 연산의 횟수 : a : 2, b : 2, c : 2
n = 10일때, 연산의 횟수 : a : 2, b : 20, c : 200
n = 1000일때, 연산의 횟수 : a : 2, b : 2000, c : 2000000
====> n이 작을때는 속도에 문제가 없다 그래서 복잡도 분석은 n이 충분히 큰 경우에만 관심있음!
4. 입력의 특성에 따른 효율성(최선, 최악, 평균)
* 입력의 종류 또는 구성에 따라 다른 특성의 실행시간
- 최선의 경우: 실행시간이 가장 적은 경우, 알고리즘 분석에서는 큰 의미 없음
- 평균적인 경우 : 알고리즘의 모든 입력을 고려하고 각 입력이 발생할 확률을 고려한 평균적인 실행시간을 의미하는데 정확히 계산하기 어렵다.
- 최악의 경우 : 입력의 구성이 알고리즘의 실행시간을 가장 많이 요구하는 경우를 말하는데, 가장 중요하게 사용된다.
====> 모든 알고리즘의 복잡도가 입력값의 구성 대해서 영향을 받는 것은 아니다. -> 최선 = 평균= 최악 인 경우!!!
* 입력의 특성에 따른 효율성의 예시(순차탐색)
리스트A, 찾는값key
def sequential_search(A,key): #순차탐색
for i in range(len(A)): #i: 0,1,,,len(A)-1
if A[i] == key: # 탐색 성공하면(비교연산, 기본연산)
return i # 인덱스반환
return -1 # 탐색 실패하면 -1 반환
최선 : 찾는 값이 맨 앞에 있을 경우 ====> Tbest(n) = 1
최악 : n번째에 값이 있을 경우 ====> Tworst(n) = n
평균 : 가정이 필요(최악의 경우, 고려하지 못한다는 단점) ====> Tavg(n) = (1+2+3+...+n) / n = (n(n+1)/2) / n = (n+1) / 2
● 점근적 성능 분석 방법
- 차수가 가장 큰 항이 절대적인 영향
ex)
T(n) = n^2 + n + 1
n = 1일때 : 3(n^2항이 33.3%)
n = 10 : 111(n^2항이 90%)
n = 100 : 10101(n^2항이 99%)
n = 1000 : 1001001(n^2항이99.9%)
====> 차수가 가장 큰 항이 제일 영향력이 높다, 복잡도에서는 증가율이 가장 큰 항을 찾는 것이 관건이다.
점근적 표기
- n이 무한대로 커질 때의 복잡도를 간단히 표현 : 복잡도 함수를 최고차항만을 계수없이 취해 단순화한다.
1. 빅오(복잡도 함수의 상한)
- 복잡도 함수 f(n)이 주어졌을 때, n>n0인 모든 정수 n에 대해 f(n)<=c|g(n)|을 만족하는
양의 상수 c와 자연수 n0가 존재하면 f(n) ∈ O(g(n))이다.
2. 빅오메가(하한)
- 복잡도 함수 f(n)이 주어졌을 때, n>n0인 모든 정수 n에 대해 f(n)>=c|g(n)|을 만족하는
양의 상수 c와 자연수 n0가 존재하면 f(n) ∈ Ω(오메가)(g(n))이다.
3. 빅세타(상한인 동시에 하한)
- 복잡도 함수 f(n)이 주어졌을 때, n>n0인 모든 정수 n에 대해 c1|g(n) <= f(n) <= c2|g(n)|을 만족하는
양의 상수 c와 자연수 n0가 존재하면 f(n) ∈ Θ(g(n))이다.
====> 셋 다 같은 의미로 이용되는 경우가 많디.
복잡도 함수의 최대 변화율에 대해서는 모든 점근적표기법이 가능하다
빅오 표기법은 더 큰 변화율이 큰 함수로 표기가 가능하지만 그럴 이유가 없다(사용되지 않는다)
빅오메가 표기법은 더 작은 변화율이 큰 함수로 표기가 가능하지만 그럴 이유가 없다(사용되지 않는다)
n에 대한 식으로 복잡도 함수가 표현이 가능한 알고리즘은 대부분 빅오, 오메가, 세타 모두 표현 가능
↘ 빅오 >> 빅세타 >>>>>>>>>>>>>>>> 빅오메가 (사용순)
다단계 알고리즘의 복잡도
T1(n) = n^2 , T2(n) = n , T3 = 1
→ T(n) = T1(n) + T2(n) + T3(n)
→ O(Tn)) = O(n^2 +n+1) = O(n^) = max(O(n^),O(n),O(1))
점근적 성능 클래스들
O(1) < O(logn)로그 < O(n) < O(nlogn)선형로그 < O(n^2) < O(n^3) < O(2^n)지수형 < O(n!)팩토리얼형
복잡도 분석 - 반복알고리즘
1. 입력의 크기를 나타내는 파라미터를 결정한다
2. 기본연산을 찾는다.(보통 반복 루프의 가장 안쪽에 있다.)
3. 연산의 횟수가 입력 크기에 의해서만 결정되는 지 살핀다.
4. 복잡도 함수 T(n)구하기
5. T(n)을 풀고 증가속도를 계산
* 리스트 중복 항목 탐색
def unique_elements(A):
n = len(A)
for i in range(n-1):
for j in range(i+1, n):
if A[i] == A[j]:
return False
return True
입력의 크기 : 리스트의 크기 = len(A)
기본연산 : 비교 연산
복잡도
- 최선 : 1->O(1)
- 최악(for문 다 돌 때) : (n-1) + (n-2) + ... + 1 = n(n-1) / 2 ==> O(n^2)
- 평균 : ( n(n-1) / 2 + .... + 1 ) / n(n-1) / 2 ==> O(n^2)
* 자연수의 2진수 변환시 비트수 (반복구조)
def binary_digits(n):
count = 1
while n > 1:
count = count + 1
n = n//2
return count
입력의 크기 : n ( n크기따라 반복횟수 결정)
기본연산 : 4 이지만 1이랑 똑같다
복잡도 -> 최선, 최악, 평균 동일
∵ O(log2n)
* 자연수의 2진수 변환 시 비트수(순환구조)
def binary_Digits(n):
if n<= 1:
return 1
else:
return 1 + binary_Digits(n//2)
복잡도 순환 관계식
n > 1일때, f(n) = f(|n/2|) + 1 ====> T(n) = T(|n/2|) + 1
n = 1일때 f(1) = 1 ====> T(1) = 0(n이 1일때는 연산이 없다.)
복잡도 : O(log2n)
복잡도분석 - 순환 알고리즘
1. 입력의 크기를 나타내는 파라미터 결정
2. 기본연산을 찾는다
3. 입력의 크기에 의해서만 연산의 횟수가 결정되는지 살핀다.
4. 기본연산의 실행횟수를 구하기 위한 순환 관계식 T(n)을 구한다. ==> 반복문과의 차이점
이때 초기조건도 찾아야함
5. 순환관계식(점화식)을 풀거나 증가속도를 계산한다.
* 팩토리얼 계산문제
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
순환관계식(점화식)
==> n = 0 일때 : F(n) = 1
==> n > 0 일때 : F(n) = F(n-1) * n
● 복잡도 함수의 순환관계식
T(n) = T(n-1) + 1
T(0) = 0
● 연속대치법에 의한 풀이
T(n) = T(n-1) + 1
=[T(n-2) + 1] + 1 = T(n-2) + 2
=[T(n-3) + 1] + 2 = T(n-3) + 3
...
=T(n-n) + n = T(0) + n
● 점근적 복잡도 : O(n)
* 반복구조의 팩토리얼 알고리즘
def factorial(n):
result = 1
for k in range(n, 0 , -1):
result = result * k
return result
복잡도 똑같이 O(n)
반복문이 효율성은 더 높다.
* 하노이의 탑 퍼즐
N개의 쌓인 원반들은 Start기둥에서 to기둥으로 옮긴다.
Hanoi(N,start,tmp,to) = Hanoi(N-1,start, to , tmp) + move(N,start, to) + Hanoi(N-1, tmp,start,to)
====> T(N) = T(N-1) + 1+ T(N-1)
순환적 전략
def honoi_tower(n,fr, tmp, to):
if (n==1):
print("원판 1 : %s --> %s" %(fr,to))
else:
hanoi_tower(n-1, fr, to, tmp) #첫번째에서 중간으로
print("원판 %d: %s --> %s" %(n,fr,to))
hanoi_tower(n-1,tmp,fr,to)#중간에서 마지막으로
T(n)
====> n = 1일때, 1
====> n >1일때, T(n-1) + 1 + T(n-1)
복잡도 : O(2^n)
'개발일기 > Python' 카테고리의 다른 글
[Python] 알고리즘 - 완전탐색 (0) | 2023.04.24 |
---|---|
[Python] 기본적인 자료구조 - 그래프(Graph) (0) | 2023.04.24 |
[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘) (0) | 2023.03.14 |
[Python] 알고리즘 - 최대값찾기 (0) | 2023.03.14 |
[Python] 기본적인 자료구조 - 리스트(list), 스택, 큐 (0) | 2023.03.14 |