개발하는 멍정이야기

Quicksort 가장 첫번째 array의 값(pivot)을 기준으로 더 작은 값과 큰 값으로 나누어 정렬함 //Quicksort void quicksort(index low, index high) { index pivotpoint; if(high > low) { partition(low, high, pivotpoint); //pivotpoint를 기준으로 정렬 quicksort(low, pivotpoint-1); // pivot보다 큰거 quicksort(pivotpoint+1, high); //pivot보다 작은거 //partition void parititon(index low, index high, index &pivotpoint) { index i, j; keytype pivotitem; piv..

The Master Theorem(마스터 정리) 이런 경우에서 시간복잡도를 편하게 구할 수 있는 공식! where a > b> 1 and n is a no -negative integer. case1. a - ε라면 시간복잡도는 오른쪽과 같다. case2. a랑ε가 같은 경우 시간복잡도는 오른쪽과 같다. case3. a + ε이고 중간의 수식을 만족하는 C가 1보다 작다면 시간복잡도는 오른쪽과 같다. Example case1 case2 case3 Auxiliary Master Theorem case3의 C < 1을 만족하지 못하는 경우

DIvide and Conquer Approach - Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다. - Conquer : 작아진 인스턴스를 해결한다. - Combine : 해결한 인스턴스를 재조립한다. -> Top-down approach(하향식 접근법) Binary Search Algorithm Design - 검색 범위를 줄여가며 탐색 - Problem : 크기가 n인 sorted array S에서 key x는 어디에 있는가? - Input(parameter) : 양수 n, 1부터 n까지의 값을 갖고 있는 정렬된 내림차순이 아닌 배열 S(sorted array) + non-decreasing order(비내림차순) : 내림차순이 아니다 != 오름차순 ex. 1, 5, 6..

Big O (빅오) 정의 : 점근적 상한선 주어진 복잡도 함수 c×f(n)에 대해 음이 아닌 정수 n이 N보다 크고 양수인 정수 c가 존재한다면 O(f(n))은 g(n)보다 큰 함수들의 집합이다. => g(n) ≤c×f(n) g(n)이 알고리즘에 대한 시간복잡도라면 결국 알고리즘의 시간복잡도의 최대값은 f(n)보다 클 수 없기 때문에 g(n)은 O(f(n))이라고 할 수 있다. -> g(n)은 c×f(n)보다 느리게 실행될 수 없기 때문 ∴ g(n)의 시간복잡도는O(f(n))이다. Example take c = 11 and N = 1 => 1^2+10*1 == 11(1^2)take c = 2 and N = 10 => 10^2+10 < 2(10^2) 아무튼 이런 시간복잡도를 갖고 있는 알고리즘은 n^2의 ..

Analysis of Algorithms 시간복잡도 분석(Time complexity analysis) - input size에 따라 얼마나 작동하는지 결정. - CPU, OS, 프로그래밍언어와 독립적임 평가지표(Metrics) Basic operation - Comparisons, assignments, etc. (비교를 얼마나 했는지, 할당을 얼마나 했는지?) Input size - The number of elements in an array - The length of a list - The number of columns and rows in a matrix - The number of vertices and edges in a graph 아무튼 기타 등등 시간복잡도에 영향을 주는 것들? Eve..

Problem Description(문제 설명) - Problem(문제) - Parameters : 문제 해결을 위한 변수 (S, n, x ...) - Instance : Parameters의 구체적인 변수 ? (ex. S = [10, 2, 4 , 46, 75]) - Algorithm : 문제 해결 방법 Pseudo code vs C++ - 문법을 지킬 필요가 없다. // 완벽한 코드로 작성하지 않고 알고리즘만 표현하면 됨 - 수학적 문법도 자유롭게 적을 수 있다 // low