[알고리즘] 알고리즘의 개념

1. 알고리즘이란?

문제 해결을 위한 단계적 절차

2. 좋은 알고리즘/데이터구조란?

공간복잡도, 시간복잡도가 낮은 것
공간복잡도 : 기억장소 사용량
시간복잡도 : 알고리즘과 데이터구조 작업에 소요되는 실행시간
최근엔 HW 발전으로 메모리 부담이 적어서 일반적으로 시간 복잡도에 집중한다.

3. 실행시간이란?

입력을 출력으로 변환하는 과정에서 걸린는 시간
best case < average case < worst case 순으로 많이 사용한다.

4. 실행시간을 추정 방법

• 실험적 방법 : 프로그램 작성 & 실험해서 시스템콜(시작 시간 - 끝 시간)로 측정.
  • 한계 : 모두 구현해야하는 어려움, 실험에 포함되지 않은 입력의 가능성, SW/HW 환경 차이
• 이론적 방법 : 의사코드(pseudo code)로 원시작업의 수를 입력크기 n에 대한 함수로 나타내기
  • 원시작업(알고리즘 기본 계산들)이 동일한 상수시간이 소요된다고 가정
    e.g. 산술식/논리식(EXP), 치환(ASS), 배열원소 접근(IND), 메소드 호출(CAL), 메소드에서 반환(RET)
  • 증가율을 기준으로 사용
    HW, SW 환경변화에도 증가율을 변하지 않는다.
  • 원시작업 수가 n, 가장빠른 원시작업 실행시간이 a, 가장 느린 원시작업 실행시간이 b이면
    an <= 실행시간 <= bn

5. 실행시간 증가율 표기법

• BigOh: 증가율의 상한
• BigOmega: 증가율의 하한
• BigTheta : 빅오이자 빅오메가

주로 가장 단순한 표현 사용

6. Big Oh 계산 요령

• 상수 : O(c), O(1)
• 차수 d이니 다항식 : O(d)
• 다중 원시작업 : O(1) - 모두 더해도 상수
• 반복문 : 반복문 실행시간 * 반복 횟수
• 연속문 : 최대값
• 조건문 : 큰 것

7. 재귀 알고리즘

자기 자신을 사용하여 정의된 알고리즘

• 재귀 케이스 + 베이스 케이스로 구성
  재귀 케이스 : 작아진 부문제들 호출
  베이스 케이스 : 충분히 작아지면, 호출 없이 직접 해결
• 베이스 케이스를 향하는 방향으로 진행
• 꼭 필요할 때만 사용하기
  저장, 호출, 리턴 등으로 호버헤드 발생이 빈번하다. 따라서 연상량 차이가 크거나 문제 자체가 재귀적으로 정의된 경우 등에만 신중히 사용하기.

---

✨ 수학적 배경

• 크기 비교

  $c < log n < log^2n < n < n log n < n^2 < n^3 < 2^n$

• 합계

  $\sum^{n}_{i=0} a^i = {(1-a^{n+1}) \over (1-a)}, \sum^{n}_{i=1} = {n(n+1) \over 2}, \sum^{n}_{i=1} i^2 = {n(n+1)(sn+1) \over 6}$

• 로그

  $log_b (xy) = log_b x + log_b y, \quad log_b (x/y) = log_b x - log_b y \\ log_bx^a = alog_bx, \quad log_ba = {log_xa \over logxb}$

• 지수

  $a^{b+c} = a^ba^c, \quad a^{b-c} = {a^b \over a^c}, \quad a^{bc} = (a^b)^c, \quad a^{log_a^b} = b$