CHAPTER07 - 알고리즘 실용화, 가까운 예로 보는 이론,연구의 실전 투입

강의 19 알고리즘과 평가

• 데이터 규모와 계산량 차이
  • 소규모 데이터에서는 O(n) 알고리즘을 사용하더라도 감당 가능
  • 데이터 건수가 늘어날 수록 차이가 점점 커짐

 

• 알고리즘이란?
  • 적당한 값을 입력하면 명확하게 정의된 계산절차에 따라 값이 출력으로 반환되는 것
  • 탐색 값을 입력하여 탐색이 이루어지면 그건 '탐색 알고리즘'
  • 넓은 의미 : 처리의 흐름 (domain logic)
  • 좁은 의미 : 정렬이나 탐색, 해시법과 같은 계산문제의 해법

 

• 알고리즘을 배우는 의의 - 컴퓨터의 자원은 유한, 엔지니어의 공통언어
  • CPU나 메모리 등 컴퓨터의 자원은 유한하다.
  • 엔지니어의 공통언어로 작용한다.
    • 그 부분은 '해시'로 이뤄졌다 라고 하면 대부분 알아먹는다.
  • 알고리즘을 알아둠으로써 새로운 문제에 대처 가능

 

• 알고리즘 평가 - Order 표기
  • 입력크기가 n 일때 대략적으로 이정도의 계산량이 소요됨을 표기하는 기법
  • 해시의 경우 n에 의존하지 않으므로 O(1)
  • 선형 탐색은 n번 탐색해야 하므로 O(n)
  • 이분 탐색은 O(log n)
  • 계산량
    • 시간 계산량 (실행시간, 단계 횟수)
    • 공간 계산량(메모리 사용량)

 

• 알고리즘과 데이터 구조(자료 구조)
  • 데이터 구조(자료 구조)
    • 배열, 트리, 힙 ...
    • 알고리즘에 자주 사용하는 조작에 맞춰 선택
  • 알고리즘에서 자주 사용하는 조작에 맞춰 데이터 구조를 선택할 필요가 있다.