본문 바로가기

C, C++/Data Structure & Algorithm in C2

[자료구조] 합병정렬(Merge Sort) - C언어 #합병정렬 - Merge sort는 분할정복법을 사용하여 정렬하는 알고리즘이다. - 분할 단계: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 - 정복 단계: 각각의 작은 문제들을 순환적으로 해결 - 합병 단계: 작은 문제들의 해를 합하여(merge) 원해 문제에 대한 해를 구함 #Pseudo code function mergeSort(list, left, right) middle = (left+right) / 2 #l과 r의 중간 지점 계산 mergeSort(list, left, mid) #전반부 정렬 mergeSort(list, mid+1, right) #후반부 정렬 merge(list, left, mid, right) #합병 #시간 복잡도 - 데이터 크기가 n 일때, mergeSort 는.. 2020. 10. 4.
[자료구조] 점근표기법(asymptotic notation) 점근표기법(asymptotic notation) O (빅-오) 점근적 상한에 대한 표기법. O(g(n))O(g(n))은 g(n)g(n)의 증가율보다 작거나 같은 함수들의 집합이다. 예를 들어 O(n^2)에는 O(1),O(n),O(nlogn)O(1),O(n),O(nlog⁡n) 등이 포함된다. 주어진 알고리즘의 증가율보다 크거나 같은 최소의 증가율을 찾는 것이 목적. #Big O 표기법 이해하기 f(x) ≤ c*g(x)을 증명할 수 있으면 f(n) = O(g(n))는 참이다. 예시 f(x) = 2x^2+3, g(x) = x^2 일때, f(x) = O(g(x))는 참인가? f(x) = O(g(x)) is true when c=3 x≥2 #O(1),O(n),O(logn)O(n^2),O(n^3) 비교 Ω (빅-오.. 2020. 10. 2.

티스토리툴바