제 7장: 알고리즘의 계산량(1)

72. 알고리즘의 계산량: 시간 계산량, 영역 계산량

• 알고리즘의 성능(얼마나 효율적인가)을 평가: 시간 계산량과 영역 계산량이 기준
• 시간계산량
  • 해당 알고리즘 실행 시 소요시간
  • 연산, 조건 비교, 변수 대입 등의 조작(단계)들을 하나의 단위로 삼아 각 실행횟수로 측정(프로그램 실행 및 종료시간까지의 시간 측정의 경우 컴퓨터 성능 혹은 주변기기 / 데이터 입출력 소요시간에 영향을 받기 때문에 적절하지 않음)
• 영역 계산량
  • 해당 알고리즘 실행 시 사용되는 공간적 자원의 크기
  • 상수 영역, 변수 영역, 배열 영역, 스택 등 작업 영역 등의 총 합계(=메모리 영역)

73. 시간 계산량 → 연산, 조건 비교, 대입 등 조작 횟수로 측정

• 1~N의 합계를 구하는 계산 예시
  • 방법1: 하나하나 더해 합을 계산
    • 1단계: 합계 저장 변수 SUM을 0으로 초기화
    • 2단계: 더할 값을 저장하는 변수 VALUE에 1 대입
    • 3단계: 변수 VALUE가 N보다 작거나 판정 결과가 참이라면 4~5단계를 반복
    • 4단계: SUM에 VALUE값 더함
    • 5단계: VALUE 값을 1 씩 증가
    • 계산량: 각 단계는 다음 횟수만큼 실행
      • 1단계→1회, 2단계→2회, 3단계→N+1회, 4단계→N회, 5단계→N회 ⇒ 총 3N+3
  • 방법2: N(N+1)/2로 계산
    • 1단계: N과 1을 더함
    • 2단계: N과 1단계에서 구한 값을 곱함
    • 3단계: 2단계에서 구한 값을 2로 나눔
• 방법 1: 3N+3회 실행(N값에 비례해 커짐) → 비효율적
• 방법 2: 3회 실행 → 효율적