[Programmers-python algorithm] - 4강

PROGRAMMERS - PART4 RECURSIVE ALROTIGHM

Recursive algorithm - 기초

• 재귀 알고리즘은 알고리즘의 이름이 아니라 '성질' 이다
• 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법 ex ) sum(n)=sum(n-1)+n
• 재귀알고리즘 에서는 종결조건이 중요하다. (Trivial case)
• 재귀함수(Recursive function)이란?
  • 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것.
  • 생각보다 많은 종류의 문제가 재귀적으로 해결이 가능하다. (Recursively)
    ex ) Binary Tree
    Tree 탐색 : 10을 찾으시오 --> 재귀적인 방법으로 이용 가능함.

Recursive function을 호출할 때는 종결조건이 매우 중요하다!!

• 인자로 주어진 n이 특정 조건일 경우--어떠한 처리 , 아닐 경우 -- 재귀 처리
• 자연수의 합을 구하는 함수를 3 가지 방법으로 구현해 보고 세 가지 방법의 속도 차이를 비교해 보았다.

# Ex 1) 자연수의 합 구하기
# 1~n 까지의 자연수의 합을 구하시오
# s=1+sum(n-1)

## Solution 1 - recursive version
import time
k=2000


def summation(n):
    if n <=1:     ## Trivial case
        return 1 
    else : 
        return n+summation(n-1) ## if thet isn't n<=1 condition, it'll go to - limt

st=time.time()
for i in range(k):
    summation(i+1)
elapse1=time.time()-st
print(elapse1)

## 결과 : 0.5566554069519043

## -------------------------------------------------------

## Solution 2 - iterative version
def sum(n):
    s=0
    while n>=0:
        s+=n
        n-=1
    return s
st2=time.time()
for i in range(k):

    sum(i+1)
elapse2=time.time()-st2
print(elapse2)

## 결과 : 0.37777066230773926

## -------------------------------------------------------

## Solution 3 - Use mathematical formulars

def sum(n):
    return n*(n+1)//2

st3=time.time()

for i in range(k):
    sum(i+1)
elapse3=time.time()-st3
print("{0:f}".format(elapse3))

## 결과 : 0.001992

## -------------------------------------------------------

print('elapse 1 : {0:f}  elapse 2 : {1:f} elapse 3: {2:f}'.format(elapse1,elapse2,elapse3))

결과 : elapse 1 : 0.556655  elapse 2 : 0.377771 elapse 3: 0.001992

Solution 1, 2 3 효률 비교

Solution 1 : Resulsively version

• 복잡도 O(n) n에 따라서 함수 호출이 증가하므로, n에 비례하는 복잡도를 갖는다.
• 함수를 다시 호출하고 return을 반복하므로 효율성 떨어짐
• 2000번 반복 시 elapse 1 : 0.556 sec 로 제일 오래걸림
  Solution 2 : Iteratively version
• 복잡도 O(n) n에 비례하여 순환문 증가
• 하지만 Solution 1처럼 return을 반복하지는 않는다는 점에서 조금 더 효율적?
• 200번 반복 시 elapse 2 : 0.377 sec 로 Solution 1 보다 1.6배 빠름
  Solution 3 : Mathmatical methode
• 복잡도 O(1)
• algorithm 이라기 보기 어렵지만, 복잡도 제일 낮음
• 2000번 반복 시 elapse 3 : 0.00199 로 제일 빠름

** Alrotighem 고려 시 복잡도도 중요하지만 효율성 측면도 유념해야 한다.

Practice 문제

• fibonacci 수열을 recursively version 과 Iteratively version으로 구현.
• 코드 구현은 아래의 링크를 통해 확인할 수 있다.

03_fibonacci_by_recursive.py
03_fibonacci_by_iterative.py