東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年2月実施 問題2

标签：

• Tokyo-University
• Bucket-Sort

Author

kainoj

Description

Consider the Java program below to sort an array $A$ in an ascending order. $M$, $N$, and $K$ are positive integers, and $A$ is an array of $N$ nonnegative integers where $0 \leq A[i] < M$ for all $i \in \{0, \dots, N-1\}$.
In this program, list is a class of an integer list with the following methods:

• lst.size(): returns the number of elements in the list lst.
• lst.get(i): returns the element at the $i$-th position in the list lst (the position number starts from 0).
• lst.insert(i, x): inserts $x$ to the list lst at the $i$-th position.

$B$ is an array of size $K$, whose elements are all initialized to empty lists. Suppose that the execution time of each of the above methods is constant. You can ignore overflow errors.

void mysort(int M, int N, int K, int[] A, list[] B) {
    for (int i = 0; i < N; i++) {
        int m = A[i] * K / M;
        int j = 0;
        for (; j < B[m].size(); j++) {
            if (A[i] <= B[m].get(j)) {
                break;
            }
        }
        B[m].insert(j, A[i]);
    }
    int i = 0;
    for (int m = 0; m < K; m++) {
        for (int j = 0; j < B[m].size(); j++) {
            A[i] = [ blank X ];
            i = i + 1;
        }
    }
}

Answer the following questions:

(1) Answer an appropriate expression to fill the blank $\boxed{\ \ X\ \ }$.

(2) Let $C$ be the number of times the line $6$ is executed. Answer the largest value of $C$ in terms of $N$ and $K$. Also, answer the expected value of $C$ in terms of $N$ and $K$, assuming that $A[i]$ is distributed independently uniformly randomly over the set $\{0, \ldots, M-1\}$. Suppose that $K \ll M$ for this question.

(3) Explain how the expected running time of this program varies when $K$ changes, assuming that $A[i]$ is distributed independently uniformly randomly.

(4) Discuss advantages and disadvantages of this algorithm in comparison to the quicksort algorithm.

题目描述

题中 Java 程序用于将数组 $A$ 按升序排序。$M,N,K$ 为正整数， $A$ 含 $N$ 个非负整数，且对所有 $i\in\{0,\ldots,N-1\}$ 均有 $0\le A[i]<M$。list 是整数列表类，size() 返回元素数， get(i) 返回从 $0$ 开始编号的第 $i$ 个元素，insert(i,x) 在第 $i$ 个位置插入 $x$；这些方法均视为常数时间。$B$ 是长度为 $K$ 的数组，每个元素初始为空列表。 忽略整数溢出。

程序先按

$$m=A[i]K/M$$

把每个元素分配到桶 $B[m]$，并通过顺序扫描把它插入桶内的有序位置；随后按桶号从小到大把各桶元素写回 $A$。回答下列问题。

（1）给出填入空白 $\boxed{X}$ 的合适表达式，使程序正确写回排序结果。

（2）令 $C$ 为程序第 6 行的执行次数。用 $N,K$ 表示 $C$ 的最大值；再假设每个 $A[i]$ 独立地在 $\{0,\ldots,M-1\}$ 上均匀分布，并假设 $K\ll M$，求 $C$ 的期望。

（3）在上述独立均匀分布假设下，说明程序的期望运行时间如何随 $K$ 改变。

（4）与快速排序相比，讨论该算法的优点和缺点。

Kai

Setting of the problem: we got $N$ element and $K$ buckets.

(1)

B[m].get(j)

(2)

The input sequence might be in an increasing order and all elements might fall into one bucket. Thus, line $6$ will be executed:

$$C = 0 + 1 + \cdots + (n-1) = \frac{n(n-1)}{2}$$

times. Note that it has to be an increasing order, because items are being inserted at the beginning of a bucket. If we wanna do evil, we must make every item traverse the whole bucket, until the end. It is possible when every inserted item is bigger than any element in the bucket, that is, input sequence is of increasing order.

(3)

Let $n_i$ denote size of $i$-th bucket. Line $6$ is de facto an insertion sort, which means that $i$-th~bucket will be sorted in $O(n^2)$. Total running time will be to:

$$C = \sum_{i=1}^{K} O(n_i^2)$$

Taking expectation:

$$\mathbb{E}(C) = \mathbb{E}[\sum_{i=1}^{K} O(n_i^2)] = \sum_{i=1}^{K} \mathbb{E}[O(n_i^2)] = \sum_{i=1}^{K} O(\mathbb{E}[n_i^2])$$

What is $[\mathbb{E}n_i^2]$? Note that, by definition $Var(X) = \mathbb{E}[X^2] - (\mathbb{E}X)^2$ for any random variable $X$. Let $X_{i,j}$ be an indicator random variable:

$$X_{i,j} = \begin{cases} 1 & \text{element $j$ went to bucket $i$} \\ 0 & \text{otherwise} \end{cases}$$

$$n_i = \sum_{j=1}^{N} X_{i, j}$$

Since we have $K$ buckets and every of them is equally likely, probability of "going to bucket $i$" is $\frac{1}{K}$. Thus, expectation of $n_i$ is:

$$\mathbb{E}(n_i) = \sum_{j=1}^{N} \mathbb{E}(X_{i, j}) = \frac{N}{K}$$

We can also notice, that, $n_i$ is just a binomial random variable with expectation $np$ and variance $np(1-p)$. Here a trial is mapping an item into bucket, and the success is placing it into $i$-th bucket. There are $n=N$ trials and probability of success if $\frac{1}{K}$.

$$\begin{aligned} \mathbb{E}[n_i^2] = Var[n_i] + (\mathbb{E}[n_i])^2 &= N\frac{1}{K}(1-\frac{1}{K}) + (\frac{N}{K})^2 \\ &= \frac{N^2 + NK - N}{K^2} \end{aligned}$$

Finally:

$$\begin{aligned} \mathbb{E}[C] = O(\sum_{i=1}^{K}\mathbb{E}[n_i^2]) = O(\sum_{i=1}^{K} \frac{N^2 + NK - N}{K^2}) = O(\frac{N^2}{K} + N) \end{aligned}$$

The following contribute to total expected running time:

• finding a bucket for each element $O(N)$
• sorting each bucket, $O(\frac{N^2}{K} + N)$
• for each bucket, getting its content: $O(K\frac{N}{K}) = O(N)$

Total running time:

$$O(\frac{N^2}{K} + 3N)$$

When $K$ is $O(N)$, then we get $O(N)$ expected running time. When $K$ is $O(1)$, then the running time is $O(N^2)$.

(4)

• BS is stable, QS isn't
• BS isn't in-place, QS is
• BS runs $O(N)$ expected, QS is $O(NlogN)$
• BS has upper limit on keys, QS hasn't