시간복잡도
1. n ≥ n0 인 모든 n 에 대하여 f(n) ≤ c · g(n)을 만족하는 양의 상수 c, n0 이 존재하 면 f(n) = O(g(n))이다.(점근적 상한) -최악의 경우이기 때문에 많이사용
2. n > n0 인 모든 n 에 대하여 f(n) ≥ c · g(n)을 만족하는 양의 상수 c, n0 이 존재 하면 f(n) = Ω(g(n))이다.(점근적 하한) -최선의경우
3. n > n0 인 모든 n 에 대하여 c1 · g(n) ≤ f(n) ≤ c2 · g(n) 을 만족하는 양의 상수 c1, c2, n0 이 존재하면, 즉 f(n) = Ω (g(n)) = O(g(n))이면 f(n) = Θ (g(n))이다. -평균적 경우
실행시간 O(n^2)
1.bubble sort
-거품처럼 최댓값/최솟값을 밀어보낸다
2.selection sort
-최솟값/최댓값을 찾아 앞에둠
-n-1부터 1번까지 줄여나가면서
3.insert sort
-이진탐색을 이용하면 O(nlogn)에 가깝다고하나 (시간복잡도를 실제로 줄여줌)
-실제로는 O(n^2)의 시간복잡도를 가진다 .
-list 에 어올리는 정렬
-최선의 경우 O(n)
-최악의 경우 O(n)
-맨앞의 값과 비교하며 작으면 넣어준다.
실행시간 bit seta O(nlogn)
1.heap 정렬
-but 1,2, .... n 까지 정렬보다는 최대/최소를 구할때 좋음
-min/max힙에 따라 갈림
-우선순위 큐와 어올린다.
-가장큰 값 몇개만 필요한 경우에 어올린다.
2.merge sort
-합병정렬
-avg,best,worst 모두 O(nlogn)
-트리 구조처럼 devide/merge 생각해보면 logn/n이다
-inversion(역전되있는 순서쌍을 구하기좋음)
-한 개까지 분할 ->머지할 때 두쌍 비교 해가면서 값을 넣음 , 왼쪽 다넣었으면 오른쪽 넣으면 됨
3.quick sort
-pivot을 정하고 왼쪽에서 I, 오른쪽에서 j선택
-i는 왼쪽에서 pivot보다 큰값, j 는 pivot보다 작은값, 교차되기전에 둘이 바꿈
-big o(n^2) big seta(nlogn)
'Computing > Datastructure' 카테고리의 다른 글
자료구조 collection (0) | 2018.10.18 |
---|