Algorithm5 [Algorithm] Heap Sort 소스코드 #include #include using namespace std; void heapify(int* a, int pos, int size) { int l = pos * 2 + 1; int r = pos * 2 + 2; int mx_idx = pos; if (l a[mx_idx]) mx_idx = l; if (r a[mx_idx]) mx_idx = r; if (mx_idx != pos) { swap(a[pos], a[mx_idx]); heapify(a, mx_idx, size); } } void buildHeap(int* a, int size) { for (int i = size/2 ; i >= 0; --i) { heapify(a, i.. 2020. 10. 26. [Algorithm] Merge Sort 소스코드 #include #include using namespace std; const int MX = 50001; int a[MX]; void merge(int *a, int left, int mid, int right) { int tmp[MX], pos = left; int u = left, v = mid+1; while (u 2020. 10. 24. [Algorithm] Quick Sort 소스코드 #include #include using namespace std; const int MX = 50001; int partition(int* a, int left, int right) { int pivot_idx = (left + right) / 2; int pivot_val = a[pivot_idx]; swap(a[right], a[pivot_idx]); int cnt = left; for (int i = left; i < right; ++i) { if (a[i] 2020. 10. 24. [Algorithm] Quick Selection 소스코드 #include #include using namespace std; const int MX = 5000001; int partition(int* a, int left, int right) { int pivot_idx = right; int pivot_val = a[pivot_idx]; swap(a[pivot_idx], a[right]); int cnt = left; for (int i = left; i < right; ++i) { if (a[i] 2020. 10. 23. [Algorithm] Master Theorem (feat. Quick Selection) 마스터 정리는 알고리즘을 재귀적인 점화식으로 표현하여 알고리즘의 동작시간을 점근적으로 계산할 수 있다는 정리입니다. 정해져있는 일종의 템플릿에 값만 넣으면 되기 때문에 계산하는 것이 어렵지 않지만 마스터 정리는 만능이 아니라 모든 재귀식에 대한 시간복잡도를 구할 수는 없습니다. # Master Theorem 마스터 정리를 간단한 형태로 나타낸 것입니다. 여기서 a, b는 1보다 큰 양수이고, f(n)은 충분히 큰 n에 대해서 양의 함수값을 가져야 합니다. 자신의 알고리즘으로 위와 같은 점화식을 세웠다면, 점화식은 다음의 세 가지 중 한 가지를 반드시 만족하며 각각의 시간복잡도 T(n)은 아래와 같이 계산할 수 있습니다. # Time Complexity of Quick Selection 이렇게만 보면 복잡.. 2020. 10. 23. 이전 1 다음