TEAMLAB

Human knowledge belongs to the world . -AntiTrust

Home PROJECT About

(8)복잡성 - 로그, 선형, 이차방정식, 지수 연산 알고리즘

on MIT

MIT - Introduction to Computer Science and Programming in Python

복잡성

  1. 코드가 가지는 효율성에 대한 중요한 설계
  2. 코드와 효율성을 연관시키는 방법

알고리즘

1. 선형 알고리즘

루프를 한 번 돌 때, 불변의 양인 1로, 문제를 줄여나가는 경향이 있다.

e.g.1) 선형 알고리즘

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

Q. 이 함수가 한 번 도는데 얼마나 많은 단계가 드는가 ?
A. 루프를 한번 도는데 세 단계의 기본적인 일(비교, 곱셈, 뺄셈)을 한다. 루프를 b번 돌려야한다. 리턴값을 갖기까지 2+3b 단계가 필요하다

Q. 문제의 크기가 커진다면, 어떤 일이 발생하는가? cost는 얼마나 발생하겠는가?
A. 결과로써 이야기하려고 하는 것은 문제의 크기가 커질떄 증가의 비율이다. 이 떄, 점근표기라는 것을 사용해야한다. 점근표기란 문제의 크기가 점점 더 커짐에 따라, 이 증가를 표현한다. 점근 표기법은 입력값이 커지게 되면 기본적으로 함수의 성장을 제한한다.

Q. 어떻게 증가를 특징 지을 수 있는가?
A. 상한을 크게 잡는 것은 도움이 되지 않는다. 이 함수가 증가할 때, 감소하는 클래스는 order b 이다. order b의 감소를 특징으로 잡을 수 있다.

e.g.2) 선형 알고리즘

 >>> def exp2(a,b):
 ...     if b ==1:
 ...             return a
 ...     else:
 ...             return a*exp2(a,b-1)

Q. 이 코드의 복잡성은 무엇인가?
A. 반복되는 exp인 경우, 문제를 풀기 위한 사이즈가 b인 경우. 하나를 빼고 하나를 곱한다. 세 가지 단계로 이루어진 코드로 조건에 따라 함수를 반복적으로 호출한다. 이를 복귀관계라고 한다.

Q. 어떻게 멈추는가.
A. b-k = 1이거나 k = b-1일 떄 루프가 끝난다.

문제 전체를 기본적으로 말하면, 명령 b는 선형이다.

2. 로그 알고리즘

어떤 승인자로 문제를 감소시키는 것

  • 절반 감소, 3분의 1로 감소 등

e.g.3) 로그 알고리즘

 a**B  = (a*a) ** (b/2) , b 짝수
      = a*(a**(b-1)), b 홀수

e.g.4) 로그 알고리즘

>>> def exp3(a,b):
...     if b ==1:
...             return a
...     elif (b%2)*2 ==b:
...             return exp3(a*a, b/2)
...     else:
...             return a*exp3(a,b-1)
...

Q. 이 코드의 순서는 무엇인가  
A. b even, t(b) = 6 +t(b/2)  
   b odd, t(b) = 6 +t(b-1)  
               = 12 +t((b-1)/2)    

일반적으로 다른 경우에서, t에 의해서 경계를 지을 수 있다.    

t(b) = 12 + t(b/2)  
     = 12 + 12 + t(b/4)  
     = 12 + 12 + 12 + t(b/8)  
     = 12k + (b/2^k)  

b/2^k = 1 일때 루프는 멈춘다.

3. 이차 알고리즘

2배 집합, 3배 집합의 것들은 이차 알고리즘과 같다. 더블 루프 이차 알고리즘은 어떤 것의 하나의 세트를 하고 있고, 다른 몇 배의 것을 하고 있기 때문이다.

e.g.5) 이차 알고리즘

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

Q. 내부 루프의 복합성이 어떻게 되는가  
A. O(n*m)  
   if m = n, O(n**2)

4. 지수 알고리즘

문제 한 가지를 형식적으로 줄여 나가 2개 혹은 더 많은 부분의 더 작은 사이즈의 문제들로 만드는 알고리즘이다.

e.g.6) 지수 알고리즘

>>> 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)
...
>>> Towers(2,'f','t','s')
Move disk from  f to s
Move disk from  f to t
Move disk from  s to t
>>> Towers(5,'f','t','s')
Move disk from  f to t
Move disk from  f to s
Move disk from  t to s
Move disk from  f to t
Move disk from  s to f
Move disk from  s to t
Move disk from  f to t
Move disk from  f to s
Move disk from  t to s
Move disk from  t to f
Move disk from  s to f
Move disk from  t to s
Move disk from  f to t
Move disk from  f to s
Move disk from  t to s
Move disk from  f to t
Move disk from  s to f
Move disk from  s to t
Move disk from  f to t
Move disk from  s to f
Move disk from  t to s
Move disk from  t to f
Move disk from  s to f
Move disk from  s to t
Move disk from  f to t
Move disk from  f to s
Move disk from  t to s
Move disk from  f to t
Move disk from  s to f
Move disk from  s to t
Move disk from  f to t
>>>

T(n) = 1 + T(1) + T(n-1)
     = 3 + 2T(n-1)
     = 3 + 2*3 + 4T(n-2)
     = 3 + 2*3 + 4*3 + 8T(n-3)
     = 3(1+2+4+ + 2**k-1) + 2**n * T(n-k)

T(n) = 2**n  # Exponential

교수님의 메세지

  • 여러분이 알고리즘의 종류들을 알고, 알고리즘의 복잡성에 알고리즘의 성능을 매치하길 바란다.

마지막 예제를 하기 전, 2가지 가 더 있다.

  1. 점근선의 성장

    Q. 이 문제의 사이즈를 크게 만드는 것처럼 그것은 어떻게 하는걸까?
    A. 최고, 최악의 경우란 없다. 단지 계산할 뿐이다.

  2. 성장의 순서를 기억하라
    예로 들어, 입력값이 무엇인지에 따라 2차 알고리즘은 선형의 알고리즘보다 더 빨리 실행 가능하다. 하지만 특정 경우를 제외하면, 모든 입력값에 대해서 선형 알고리즘이 2차 알고리즘보다 빠를 것이라는 것은 일반적인 사실이다.

e.g.7) Search a sorted list
  • 초기단계가 무엇인지 생각해보는 방법을 보여줌
  • 특별한 데이터 구조가 이 분석과 어떻게 상호작용하는 지 보여줌 
     >>> def search(s,e):
...     answer = None
...     i = 0
...     numCompares = 0
...     while i < len(s) and answer == None:
...             numCompares += 1
...             if e == s[i]:
...                     answer = True
...             elif e < s[i]:
...                     answer = False
...             i +=1
...     print(answer, numCompares)
...
>>>

리스트의 인덱스를 하나씩 움직이는 것은 선형 알고리즘이다.
리스트를 반절로 나누어 확인하는 것은 각 단계에서 최소한 리스트의 절반을 버릴 수 있다는 것을 보장하기 때문에 올바르다.

Q. 성장 순서(Growth Order)를 어떻게 추측할 수 있는가?
A. 로그 알고리즘
왜냐하면 매번 문제들을 반으로 나누기 때문이다.

e.g.8)

  >>> def bsearch(s, e, first, last):
  ...     print(first, last)
  ...     if (last - first) < 2:
  ...             return s[first] == e or s[last]==e #코드가 강의영상에 다 안보여서 틀릴수도있다.
  ...     mid = first + (last - first)/2
  ...     if s[mid] == e:
  ...             return True
  ...     if s[mid] > e :
  ...             return bsearch(s,e,first, mid-1)
  ...     return bsearch(s,e,mid+1, last)
  ...
  >>> def search1(s,e):
  ...     print(bsearch(s,e,0, len(s) - 1))
  ...     print('Search complete')

  >>> def testSearch():
  ...     s = range(0,100000)
  ...     input('basic,-1')
  ...     print(search(s,-1))
  ...
  >>> testSearch()
  basic,-1
  False 1
  None

교수님 메세지

  • 이번 시간에 로그, 선형, 이차와 지수에 대한 알고리즘에 알아봤다. 이번 시간이 지나면 다시 얘기하지않으니 개인적으로 알고리즘의 다른 수업들을 알기를 원한다.
View Comments...