숫자 그룹을 $k$ 정렬된 그룹으로 분할

Question

나는 이 첫 번째 임무를 가지고 있습니다:
일련의 숫자가 있습니다. $S =\{ \점 \}$ 길이의 $n$.
그리고 숫자 $k$.
둘 다 $n$ 그리고 $k$ 의 힘이다 $2$ 그리고: $1 < k < n$

당신의 임무는 분할하는 알고리즘(의사 코드)을 작성하는 것입니다. $S$ ~ 안으로 $k$ 세트(각각 동일한 길이를 가짐): $S_1 , S_2 , \dots, S_k$ 그 안에 있는 모든 숫자가 $S_i$ 의 모든 숫자보다 작습니다. $S_{i+1}$ 모든 $1 \leq i \leq k-1$ 시간복잡도에서는 $O(n \cdot k)$ (작업 1 끝)

두번째 (또 다른 질문이지만 첫 번째 질문과 관련됨) 작업은 동일하지만 더 빠른 알고리즘을 제안합니다 - 의사 코드(시간 복잡도 측면)

예를 들어:

을 위한 $S = \{11,5,2,7,1,13,15,16 \}$ 그리고 $k = 4$ 나는 돌아올 것입니다 (오른쪽에서 왼쪽으로):
$\{16, 15 \} , \{13, 11 \} , \{5, 7 \} , \{1, 2\}$
이 세트 안의 숫자 순서는 특정 순서일 필요가 없습니다.

내가 갈게:
내가 시도하지 않은 것은 무엇입니까 ..하나님:

1. 버킷 정렬을 해보자고 생각했어요.

2. 어쩌면 무작위 피벗을 선택하고 다음을 수행할 수도 있습니다. 선택하다 각 그룹마다.

3. 만들다 $k$ 빈 길이 세트 $\frac{n}{k}$ 각각("사전")을 선택한 다음 $k$- 각 반복마다 더 작은 요소.

4. 만들다 $k$ 빈 길이 세트 $\frac{n}{k}$ "미리" 그런 다음 각 숫자를 첫 번째 숫자에 넣고 더 큰 숫자를 발견하면 위의 예에서와 같이 가장 작은 숫자를 다음 세트로 이동합니다(자세한 내용은 아래 참조).

이것은 내가 지금까지 가지고 있는 알고리즘입니다(4번).

먼저 빈 공간이 있습니다. $k=4$ 길이 세트 $\frac{n}{k} = \frac{8}{4} = 2$ 그러다가 온다 $11$, 그 다음에 $5$ :
$\{11 , 5 \}, \{ , \}, \{ , \}, \{ , \}$ 그런 다음 $2$ 왔는데 생각보다 작아요 $5$ 또는 $11$ 그래서 $\{11 , 5 \}, \{2 , \}, \{ , \}, \{ , \}$ 그 다음 온다 $7$ 그리고 그것은보다 크다 $5$ 그래서 그것을 교체하고 $5$ 다음 세트로:
$\{11 , 7 \}, \{2 , 5\}, \{ , \}, \{ , \}$ 등...

작동해야 하지만 실행 복잡성이 무엇인지 잘 모르겠습니다.각 세트에 대해 ($k$ 배) 달려야 해 $\frac{n}{k}$ 반복(각 하위 집합의 길이)

내가 올바르게 이해하면 아무것도 작동하지 않습니다.여기에는 시간 복잡도가 없습니다. $O(n \cdot k)$ ...
두 번째 해결책은 생각도 안 해봤는데..1차 합격을 못해서..

도와주시면 감사하겠습니다!

Answer 1

두 번째 아이디어는 거의 비슷한 것 같습니다.실제 알고리즘은 다음과 같습니다(무작위 피벗이 필요하지 않음).

1. 찾기 $i{n\over k}$모든 항목에 대한 '번째 주문 통계 $1\le i\le k$.이 작업은 $O(n)$ 매번 $k$ 값: $O(nk)$.
2. 그러한 모든 것에 대해 $i$, 값이 있는 모든 요소를 $i{n\over k}$'일과 $(i+1){n\over k}$'번째 순서 통계 $i$'번째 양동이.각각 $i$ 비용이 들 것이다 $O(n)$ 그리고 거기에 $k$ 에 대한 다른 값 $i$, 따라서 총 $O(nk)$.

두 단계 모두 소요됩니다. $O(nk)$ 따라서 전체 알고리즘은 다음에서 실행됩니다. $O(nk)$ 필요에 따라

두 번째 질문에 대한 힌트: 이 알고리즘을 거친 버전의 퀵 정렬과 결합하는 방법을 생각해 보세요.