수업 내용 정리/algorithm (2) 썸네일형 리스트형 chapter 2. divide-and-conquer 설계 전략 Divide: 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. Conquer: 나눈 작은 문제를 각각 해결한다. Combine: 해결된 해답을 모은다. => 하향식(top-down) 이분 검색: 재귀적 방식 분할: 배열을 반으로 나누어서 중앙에 위치한 값과 x를 비교해서 두 배열 중 하나를 선택 정복: 선택된 반쪽 배열에서 x를 찾는다. 시간복잡도 경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우 경우2: 일반적인 경우 - 반쪽 배열의 크기는 n/2의 같거나 작은 실수 합병정렬 합병 알고리즘 시간복잡도 분석(최악) W(h,m) = h+m-1 (예 U: 4,5,6,7 V: 1,2,3,8) 합병정렬 알고리즘 시간복잡도 분석(최악) W(h,m) = W(h) + W.. chapter 1. 알고리즘: 효율, 분석 그리고 차수 순차검색 알고리즘 배열의 수 더하기 교환정렬 행렬곱셈 이분검색 알고리즘 최대 검색횟수 : lg(n) + 1 피보나찌 구하기 재귀적 방법 문제점: 어떤 피보나찌 수를 구하기 위해 다른 피보나찌 수가 중복될 수 있다. fib(n)의 함수 호출 횟수 계산 수학적 귀납법을 통한 호출 횟수 검증 T(n) > 2**(n/2) 임을 보이자 반복적 방법 중복 계산이 없다 => 수행속도가 훨씬 빠르다! 계산하는 항의 총 개수: T(n) = n + 1 (f[0] 부터 f[n]까지) 알고리즘 분석 Every-case analysis Worst-case analysis 입력배열이 거꾸로인 최악의 상태일 때 => (n-1)*n/2 행렬곱셈 시간 복잡도 단위 연산이 for 루프에 있는 곱셈 : T(n) = n*n*n 순차검색 시.. 이전 1 다음
