chapter 1. 알고리즘: 효율, 분석 그리고 차수

순차검색 알고리즘

배열의 수 더하기

교환정렬

행렬곱셈

이분검색 알고리즘

최대 검색횟수 : lg(n) + 1

피보나찌 구하기

재귀적 방법

문제점: 어떤 피보나찌 수를 구하기 위해 다른 피보나찌 수가 중복될 수 있다.

fib(n)의 함수 호출 횟수 계산

수학적 귀납법을 통한 호출 횟수 검증

T(n) > 2**(n/2) 임을 보이자

 

반복적 방법

중복 계산이 없다 => 수행속도가 훨씬 빠르다!
계산하는 항의 총 개수: T(n) = n + 1 (f[0] 부터 f[n]까지)

알고리즘 분석

1. Every-case analysis
2. Worst-case analysis <= 주요 관심
3. Average-case analysis
4. Best-case analysis

배열의 수 더하기 시간 복잡도

• 단위 연산이 덧셈일 경우: T(n) = n
• 단위 연산이 세개의 지정문일 경우: T(n) = n + n + 1

교환정렬 시간 복잡도

• 단위 연산이 S[j]와 S[i]의 비교 일때 : (n-1)*n/2
• 단위 연산이 S[j[와 S[i]의 교환 일때 : 조건문의 연산에 따라 교환 여부가 결정된다 => 입력배열이 거꾸로인 최악의 상태일 때 => (n-1)*n/2

행렬곱셈 시간 복잡도

• 단위 연산이 for 루프에 있는 곱셈 : T(n) =  n*n*n

순차검색 시간복잡도 분석 (평균)

• 1부터 n에서 k번째에 있을 확률 1/n
• 단위 연산의 횟수 => k

복잡도 함수

큰(big) O 표기법: 점근적 상한 => 이거보단 덜 걸린다.
오메가 표기법: 점근적 하한 => 이거보단 많이 걸린다.
세타 표기법: 비슷하다

큰 O vs. 작은 o 차이점

• 큰 O - 실수 c>0 중에서 하나만 성립하여도 됨
• 작은 o - 모든 실수 c>0에 대해서 성립하여야함

알고리즘 복잡도와 컴퓨터 능력

• 알고리즘 복잡도가 cn일 경우
  현재 기계가 문제 크기 m개의 문제 해결 => 기계의 처리 속도가 2배가 된다면 2m개의 문제를 해결할 수 있다.
• 알고리즘 복잡도가 cn**2일 경우
  현재 기계가 문제 크기 m개의 문제 해결 => 기계의 처리 속도가 4배가 된다면 문제크기 2m개의 문제를 해결함
• 알고리즘 복잡도가 c2**n일 경우
  현재 m개의 문제 해결 => 처리 속도가 2배가 된다면 문제 크기 m+1 개의 문제를 해결