[Algorithmic Problem Solving Strategies] 4. 알고리즘의 시간복잡도 분석

알고리즘 문제 해결 전략 세트 국내도서 저자 : 구종만 출판 : 인사이트 2012.11.23 상세보기

알고리즘 문제 해결 전략 세트구종만 상세보기

 

4.1 도입

=========
1. 알고리즘의 속도 측정 방법

• 알고리즘의 수행 시간 = 반복문이 수행되는 횟수

4.2 선형 시간 알고리즘

=========
1. 다이어트 현황 파악: 이동 평균 계산하기

4.3 선형 이하 시간(sublinear time) 알고리즘

=========
1. logN: 입력의 크기가 커지는 것 보다 수행시간이 느리게 증가하는 알고리즘
—————-

2. 이진탐색(binary search)
—————-

4.4 지수 시간 알고리즘

=========
1. 다항 시간 알고리즘
—————-

• 변수 N, N^2, ..., N^100

2. 지수 시간 알고리즘
—————-

• 2^n

4.5 시간 복잡도time complexity

=========
1. 입력의 종류에 따른 수행 시간의 변화
——————

• 최선의 수행 시간
• 최악의 수행 시간
• 평균적인 경우의 수행 시간

2. 점근적 시간 표기: O표기(order)
——————

• 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법
• 최악의 수행시간과 관련 X

3. 시간 복잡도 분석 연습
——————

• 삽입정렬: 흔히 사용하는 O(N^2) 정렬 중 가장 빠른 알고리즘

  최선의 경우: O(N)
  최악의 경우: O(N^2)

• 선택정렬

4. 시간 복잡도의 분할 상환 분석amortized analysis
——————

4.6 수행 시간 어림짐작하기

==========
1. 주먹구구 법칙
——————
“입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다.”

2. 주먹구구 법칙 고려해야하는 요소
——————-

• 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
• 반복문의 내부가 복잡한 경우
• 메모리 사용 패턴이 복잡한 경우
• 언어와 컴파일러의 차이
• 구형 컴퓨터를 사용하는 경우

4.7 계산 복잡도 클래스: P, NP, NP-완비

===========
P: 다항 시간 알고리즘이 존재하는 문제들의 집합(ex.sort)

• 계산 복잡도 클래스Complexity class: 같은 성질을 갖는 문제들을 모아놓은 집합

NP: 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제, P문제가 포함됨

• SAT문제(satisfiability problem): 어려운 문제의 기준
  ((a||b||!c) && (!c||!a) && ((!a&&b)||(b&&!c))) && (!b||(!a&&!c))

NP-Complete: NP-Hard면서 NP인 문제

NP-hard: SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있음

+) 마스터 정리Master Theorem

• 재귀적인 알고리즘의 시간 복잡도를 계산하는 쉬운 방법
• 함수의 수행 시간이 특정 형태의 함수로 표현 될 때, 이 함수의 O 표기법을 쉽게 계산할 수 있도록 도와줌