알고리즘 1주차 중요 이론 개념 정리

1.재귀 호출

1-1. 점화식이란?

수학에서 점화식 또는 재귀식이란 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계

1-2. 팩토리얼

def factorial(n):
    if n==0:
        return 1
    return n*factorial(n-1)

1-3. 피보나치 수열

def fibonacci(n):
    if n<=1:
        return n
    return fibonacci(n-1)+fibonacci(n-2)

1-4. 하노이의 탑

원리 : 3개의 원판을 옮긴다면 2개의 원판을 다른곳으로 옮기는 것을 2번 반복하고 그 사이 제일 아래의 원판을 옮기는 회수 1이 추가 되는 원리

• 하노이 탑의 일반항 도출 과정
  

2. 시간 복잡도, 공간 복잡도

• 시간 복잡도 : 실행하는 데 필요한 시간을 평가
• 공간 복잡도 : 메모리(기억공간)과 파일공간이 얼마나 필요한지를 평가

O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ)

3. quick sort, insertion sort, merge sort, heap sort

이전에 쓴 글이 있어 링크를 남긴다.

정렬 알고리즘

3-1. quick sort를 가장 많이 쓰는 이유

• Locality

  Locality는 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스 하는 경향

Quick sort는 다른 배열을 사용하지만 quick sort는 다른 배열 사용하지 않기 때문에 Locality가 더 높다.

Ref)
https://velog.io/@eensungkim/%EC%A0%90%ED%99%94%EC%8B%9D-TIL-42%EC%9D%BC%EC%B0%A8
https://shoark7.github.io/programming/algorithm/tower-of-hanoi
https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4
https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84