분할정복(Divide and conquer),퀵정렬,병합정렬과 재귀(Recursion)

분할정복과 재귀

 

분할정복 : 복잡하거나 큰 문제를 여러 개(병렬적으로)로 나눠서 푸는 방법

분할정복 방법 진행중에 재귀가 사용될 수 있다.

 

분할정복과 재귀 코드비교

# 재귀 : 1부터 10까지의 합

def func(num):
  if num < 1:
    return 0
  else:
    return num + func(num-1)

func(10)

##########################

# 분할정복 : 1부터 10까지의 합

def func(num):
  if num == 1:
      return 1
  if num % 2 == 1:
      return func(num - 1) + num
  else:
      return func(num / 2) * 2 + (num / 2) * (num / 2) 

func(10)

---

퀵정렬과 병합정렬의 비교

퀵정렬

: 퀵정렬은 처음에 전체 탐색을 할 때 좌우로 나눠서 재귀적으로 수행하기 때문에 병합정렬보다 빠르다.

(빠르지만 성능편차가 크고 병합정렬보다 덜 안정적이다)

 

병합정렬

: 병합정렬은 분할과 교체를 반복(1개의 서브리스트가 나올때까지)

반복문을 통해 비교->정렬->교환 후 합치는 과정을 연속적으로 진행