MIT 6.00 8회차 강의후기

License

License: Creative Commons BY-NC-SA

 

1. Contents

선형 알고리즘

def exp(a,b):
    ans = 1
    while (b>0) :
            ans *= a
            b -= 1
    return ans

위와 같은 식이 있을 때 이 함수의 값을 구하기 위해서-

(ans = 1)과 (return ans)의 두가지 연산에 더해서
1. \> 연산
2. *= 연산
3. -= 연산

n회의 3가지의 단계를 거친다. 따라서 3n + 2의 단계가 필요하다. 

점진적으로 숫자가 증가함에 따라 첨가된 +2의값은 중요하지 않고, 곱해진 3 또한 중요하지 않아진다.  
여기서 중요한 것은 문제의 크기가 커질 때 증가의 비율이다.

알고리즘의 문제의 크기가 한계만큼 점점 더 커지는것에 대하여 증가비율을 특정하기 위해 점근표기를 사용한다.

 

Big-O 표기

Upper limit to the growth of function as the input gets large

 

로그 알고리즘

1. b가 짝수라면 (a*a)**(b/2)이다.

2. b가 홀수라면 a*(a**(b-1))이다. 

 

def exp(a,b):
    if b ==1:
            return a
    elif (b/2)*2 == b:
            return exp(a*a, b/2)
    else:
            return a*exp(a,b-1)

b/2*2 == b(짝수)일 때와 홀수일때 알고리즘이 나뉜다.  

이때 홀수의 경우
1. b == 1인지 확인하는 1steps
2. (b/2)*2 == b인지 확인하는 4steps
3. a*a, b/2으로 각각 return하는 1step

총 6개의 과정을 거쳐 b/2가 리턴된다. 따라서 t(b) = 6 + t(b/2)가 된다.

짝수의 경우에도 같은 과정을 거쳐 t(b) = 6 + t(b-1)이 된다.

이때 홀수로 시작했다면 b가 1개 작아지면 짝수로 변하기에  
t(b) = 6 + t(b/2) -> 12 + t((b-1)/2)가 된다.

이 식을 전개한 뒤 다시 일반화를 한다면 12k + (b/2^k)가 된다.  
(수학적으로는 맞지 않는 표기이며, 지수 알고리즘의 원리를 이해하기 위한 일반화이기에 깊게 생각하지 않는다.)

 

이차 알고리즘

def g(n,m):
    x = 0
    for i in range(n):
            for j in range(m):
                    x += 1
    return x

위와 같은 식이 있을 때 루프의 복잡성은 n * m으로 나타낼 수 있다.  
만약 n=m이라면 n^2로도 나타낼 수 있다.

 

지수 알고리즘

def Towers(size, fromStack, toStack, spareStack):
    if size == 1:
            print('Move disk from ', fromStack, 'to', toStack)
    else:
            Towers(size-1, fromStack,spareStack, toStack)
            Towers(1,fromStack,toStack,spareStack)
            Towers(size-1, spareStack, toStack, fromStack)

위와 같은 식이 있을때  
T(n) = 1 + T(1) + 2T(n-1)이 된다.  
T(1)에서는 2가지 step이 있기에 식은 3 + 2T(n-1)로 표현될 수 있다.  
3 + 2T(n-1)   
-> 3 + 2\*3 + 4T(n-2)  
-> 3 + 2\*3 + 4\*3 + 8T(n-3) 
-> ... 3\*(1+2+3+...2^k-1)+2 + 2^n\*T(n-k)

T(n) = 2^n

 

하노이탑

[재귀 - 하노이탑 정리]

 

분류된 리스트 검색

리스트를 따라서 검색하는 알고리즘의 복잡도는 len(s) (리스트의 길이)가 될 것.  
이때 알고리즘의 Big-O는 n, 즉 선형이다.

중간에 검색에 성공하더라도 복잡성을 변하지 않는다. 왜냐하면 ☆최악의 경우를 측정☆ 하기 때문이다.

Binary search를 이용하면 최소 절반을 버릴 수 있다. 이때 Big-O는 로그이다. 한번의 시행마다 1/2을 줄이기 때문이다.