1. Describe linear median finding algorithm. Show that its time complexity is Θ(n).
선형 시간(linear time) : 입력 크기에 비례하여 알고리즘이 실행되는 시간
예를 들어, n개의 원소를 가지는 배열에서 최댓값을 찾는 알고리즘이 O(n)의 선형 시간을 가진다면, 배열의 크기가 2배가 되면 실행 시간도 2배로 증가
➕ O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다
➕ O(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
1️⃣Quick Select?
Partitioning(파티셔닝)을 이용한 알고리즘
▶ Partitioning 이란?
- Pivot 이라는 하나의 숫자를 기준으로 배열의 요소를 정렬하는 방식
- Pivot 보다 작은 수는 좌측에 위치한다.
- Pivot 보다 큰 수는 우측에 위치한다.
- 이와 같은 규칙으로 배열의 요소를 정리하는 것이다.
(같은 수인 경우는 제외?)
2️⃣처음에 Median of medians 알고리즘과 퀵 선택 알고리즘의 연관성을 이해하지 못했다.
-> 퀵 선택 알고리즘에서 선정한 pivot이 너무 작거나 크다면?
partitioning이 제대로 이루어지지 않아 최악의 경우 시간복잡도 : O(n²)
-> 퀵 선택의 성능 결정 요소 : good pivot을 얼마나 빨리 찾아내는지
QuickSelect를 median of medians을 이용해서 pivot을 선정하면?
최악의 경우에도 시간복잡도 O(n)에 구현 가능!
3️⃣- Median of medians
1) Array의 size가 25 이하일 경우, Array를 sort하여 selection한다
2) Array의 Size가 25를 넘을 경우, Array를 size가 5인 n/5개의 subarray들로 분할한다.
3) 각 subarray들의 median을 찾은 후, 이를 M(medians) Array에 저장한다.
(이 때, median을 찾기 위해 sort 알고리즘을 사용해도 무방)
4) M array의 median을 quickselect using median of medians로 찾아내고(0번부터 재귀 호출) 이를 pivot으로 선정한다
5) pivot 선정 이후의 quickselect 알고리즘을 적용하여 k번째 작은 element를 반환한다
4️⃣🔥Quick-Select with median of medians
T(n/5) : Array M에서 subproblem(subarray의 medians들 중 median 찾기) 해결 : 실제 중앙값 찾
T(7n/10) : pivot(mom) 선정 후 결정된 subproblem의 최대 크기 : (n - 3n/10)
O(n) : n/5개의 배열 sort하는데 걸리는 시간( subarray n/5개 * O(1) <- 5개의 array sort 시간 )
T(n) = T(n/5) + T(7n/10) + O(n)
T(n) ≤ T(9n/10) + O(n)
=> master theorem에 의해 T(n) = O(n)
https://goodgid.github.io/Algorithm-Time-Complexity-Analysis/
알고리즘 시간 복잡도 마스터하기 feat. 마스터 정리 (Master Theorem)
Index
goodgid.github.io
https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
Master theorem (analysis of algorithms) - Wikipedia
From Wikipedia, the free encyclopedia Bounds recurrence relations that occur in the analysis of divide and conquer algorithms In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O
en.wikipedia.org
[알고리즘] Time Complexity (시간 복잡도) - 하나몬
⚡️ Time Complexity (시간 복잡도) Time Complexity (시간 복잡도)를 고려한 효율적인 알고리즘 구현 방법에 대한 고민과 Big-O 표기법을 이용해 시간 복잡도를 나타내는 방법에 대해 알아봅시다. ❗️효
hanamon.kr
https://devraphy.tistory.com/372
6. Array(배열) - Quick Select
1. Quick Select란? - 정렬되지 않은 배열에서 N번째로 크거나 작은 수를 찾을 때 사용되는 알고리즘 - N번째 수를 찾기 위해서는 다음과 같은 방법을 사용할 수 있다. 1) 전체 요소를 오름차순으로 정
devraphy.tistory.com
https://woongsios.tistory.com/194
선택문제 Quick Select
- 선택문제: n개의 값 중에서 k번째로 크거나 작은 수를 찾는 문제 - Quick Select: pivot과 작은 값, 같은 값, 큰 값으로 나누어서 찾고자 하는 수가 어디에 속해있는지 찾아나가는 방법 1. pivot 고르기 2
woongsios.tistory.com
https://2jinishappy.tistory.com/127
Quick Select를 O(n)에 구현 가능한 Median of Medians 알고리즘
2jinishappy.tistory.com/124 Array의 k번째 작은 element 찾기 - QuickSelect 알고리즘 Size가 n인 int형 Array에서 k번째로 작은 element를 찾는 방법은 여러 가지가 있다. 가장 formal하게, 배열을 sort한 뒤 인덱스가 k
2jinishappy.tistory.com
https://en.wikipedia.org/wiki/Median_of_medians
Median of medians - Wikipedia
From Wikipedia, the free encyclopedia Fast approximate median algorithm In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, most commonly quicksel
en.wikipedia.org
+)추가 참고 자료
https://gazelle-and-cs.tistory.com/58
선형 시간에 중간값 구하기 (Quick-Select & Median-of-Medians)
이번 포스트에서 함께 공부할 내용은 중간값(median)을 구하는 방법입니다. 중간값은 어떤 수열을 오름차순으로 정렬했을 때 가운데에 위치한 수를 의미합니다. 예를 들어, 수열이 \[ 4, 8, 3, 1, 6 \]
gazelle-and-cs.tistory.com
선형 시간 안에 중앙값 선택하기
최악의 경우에도 선형 시간에 중간값을 선택할 수 있는 알고리즘은 다음과 같다. * 아래는 median을 찾는 예이지만, k번째 작은 값 찾는 문제에 적용 가능하다. ``c Element select(SetOfElements S, int k)`` 중
umbum.dev
2. In hashing function, why the coefficient a should not be 0?
3. Read chapter 8.4. Solve example 8.1 in the chapter.
| [예제 8.1] 만약 키가 균일하게 분포되어 있고 n=2m이라면, 실패한 검색은 각각 2m/m = 2번의 비교만 필요하고, 성공한 검색은 평균 비교 횟수가 다음과 같다, 2m/2m + 1/2 = 3/2 |
4. Use the birthday dataset, do the followings:
4.1. Put them into your unsorted array using set.
4.2. Order them with the birth day. You should consider the following algorithms.
- Basic quick sort
Pivot X = A[0] or A[n-1]
- Intelligent quick sort
Pivot X = median of A
- Paranoid quick sort
Pivot X = E(Good choice)
- Tuple sort
1) The month comes first, and the date second
2) The date comes first, and the month second
4.3. Compare the sorting algorithms
'CS > Algorithm Assignment' 카테고리의 다른 글
| Problem Set 6 (0) | 2023.04.11 |
|---|---|
| Problem Set 3 (0) | 2023.03.21 |
| Problem Set 2 (0) | 2023.03.14 |
| Problem Set 1: Birthday Problem (0) | 2023.03.07 |