2주차 - 알고리즘의 분석

알고리즘

바람직한 알고리즘

• 명확해야 함
  • 명확성을 해치지 않으면, 일반 언어로 사용해도 무방함
  • 가능하면, 이해가 쉽고 간명하게 해야함
  • 지나친 기호의 사용은 명확성을 떨어뜨림

알고리즘 분석의 필요성

• 같은 문제에서도 알고리즘 마다 효율이 크게 차이 남
• 정렬에서 입력의 크기가 n일때, 최악의 알고리즘은 \(n^2\)의 시간을 소모함 이와 반대로, \(n\log^n\)에 비례하는
  알고리즘도 존재함
• 무결성 확인
• 자원 사용의 효율성 파악
  • 시간
  • 메모리, 통신대역…

알고리즘의 분석

알고리즘의 수행시간을 파악하기

• 수행시간에 영향을 주는 기준
  1. for / while문의 반복 횟수
  2. 특정 행이 수행되는 횟수
  3. 함수의 호출 횟수

공간 효율성과 시간적 효율성

공간적 효율성

• 얼마나 많은 메모리 공간을 필요하는지를 의미

시간적 효율성

• 얼마나 많은 시간을 필요하는지 의미

복잡도가 높을 수록 효율성이 저하됨

일반적으로 시간적 효율성이 공간적 효율성보다 더 강조됨

• 단, 공간적 효율은 무시해서는 안됨

점근적 분석

• 크기가 작은 문제
  • 효율성이 중요하지 않으므로, 비효율적인 알고리즘도 상관없음
• 크기가 충분히 큰 문제
  • 비효율적인 알고리즘에서는 비용 소요가 크므로, 효율성이 중요함

이러한 크기가 충분한 큰 문제에 대한 분석을 점근적 분석이라고 함

재귀와 귀납적 사고

• 재귀 = 자기호출
• 재귀적 구조
  • 어떤 문제 내에 크기만 다를 뿐, 구조는 같은 문제가 포함 된 것
  • 예시)
    • 팩토리얼(n! = n x (n-1)!)

병합 정렬

• 단게별로 두 그룹의 정렬된 데이터를 서로 합쳐, 정렬된 그룹으로 만들어가는 정렬
• 입력: 정수 n, 크기가 n인 배열 S[1, …, n]
• 출력: 비내림차순으로 정렬된 배열 S[1,…, n]

알고리즘의 적용 주제

• 차량 네비게이션

• 스케쥴링
  • TSP
  • 차량 라우팅
    • 한정된 차량의 수로 다수의 화물을 처리해야 할때, 배달거리를 최소화 하여 모든 화물을 처리하는 것
  • 작업 공정

• 인간 게놈 프로젝트

• 검색

• • DB, 웹사이트…
• 자원 배치
  • 부두 선적 및 창고 관리

• 반도체 설계

  
  

알고리즘의 점근적 복잡도와 차수

차수 vs 상수

• c1과 c2가 상수일 때, c1n과 c2n2를 비교하면 차수가 중요함을 알 수 있다.
• 상수 요소는 무시 할 수 있으며, 이를 정리하면 N이 무한대로 갈 때를 기준으로 평가함

점근적 표기법

1. \(O(f(n))\)⠀

• 최대, f(n)의 비율로 증가하는 함수

• 점근적 상한

• 예시

  \(O(n),⠀⠀O(nlog n),⠀⠀O(n^2)\)⠀

• \(g(n) ∈ O(f(n))\)을 관행적으로 \(g(n) = O(f(n))\)이라고 씀

• 주의점

  • 표기를 할 때 가능하면 최대한 tight하게 쓰기

    • 예시)

      ##nlogn + 5n = O(nlogn)\(이지만\)O(n^2)$$로 쓸 필요는 없음

• 사용 예시

  • 퀵 정렬(\(O(n^2)\))
  • 힙 정렬(\(O(nlogn)\))

1. \(Ω(f(n))\)

   • 정의

     • 최소, f(n)의 비율로 증가하는 함수

     • $$O(f(n))과 대칭적임

     • 점근적 하한

   • 예시 \(5n^2 + 4n = Ω(n^2)\)

     \[g(n) = Ω(f(n))\]

     • g는 f보다 빠르게 증가한다

     • 입력 크기 n에 대해 수행 시간은 g(n)이 f(n)보다 크다

2. \(Θ(f(n))\)

   • 정의

     • f(n)의 비유로 증가하는 함수

     • \(g(n) = Θ(f(n))\)에서 g의 상승률은 f의 상승률과 같음

     • 점근적 동일

   • 사용 예시

     • 선택정렬(\(Θ(n^2)\))
     • 평균(\(Θ(nlogn)\))

이진 탐색

정의

• 값을 비교하여 찾는 값이 존재하는 범위를 절반으로 줄여가며 탐색하는 알고리즘

분석 방법

• 정렬된 리스트에서 특정 값을 찾아 위치를 반환하고, 존재하지 않으면 -1를 반환함

• 이진 탐색은 이분, 둘로 나눈다는 의미로 자료를 2개로 나눠가며 값을 찾아감

특징

• 선형 탐색에 비해 효율적임
  • 자료의 수를 1000개로 가정했을 때, 선형 탐색은 모든 값을 탐색하므로, 최대 1000번을 수행하지만, 이진 탐색은 최대 10번을 탐색함
    \(log2^1000 ≒ 10\)
• 이진 탐색의 복잡도 \(O(log n)\), 순차 탐색의 복잡도 \(O(n)\)

예시

• 사전에서 단어 찾기
• 호텔에서 방의 호수 찾기