《算法导论》第2、3章部分题解

4月3日 · 2018年

《算法导论》第2、3章部分题解

Problems 2-4

a

(2,1) (3,1) (8,6) (8,1) (6,1)

b

与自然序列逆序的排列将有最多的逆序对,即{n, n-1, n-2, ..., 2, 1}

显然,逆序对的个数为
$$
(n-1)+(n-2)+…+2+1
$$
化简得
$$
\frac{n(n-1)}{2}
$$

c

逆序对的数量越多,程序运行时间越长

对于任意数组元素a[i]a[j],若i<ja[i]<=a[j],那么这不是逆序对,也不需要进行插入排序,若i<ja[i]>a[j],那么这是逆序对,因此需要进行插入排序

如果认为运行时间只与关键操作的步骤相关(这里的关键步骤指比较元素大小,以及移动元素进行插入排序),那么显然逆序对越多,需要移动的次数越多

d

用归并排序计算逆序对的个数

首先证明可行性

归并排序中的Merge操作,a[left]~a[middle]表示其中一个已排序的部分,a[middle+1]~a[right]表示另一个已排序的部分,现在需要将这两个部分合并

定义left<=i<=middle, middle<j<=right

如果a[i]<=a[j],由于满足i<ja[i]<=a[j],这不是逆序对

如果a[i]>a[j],由于满足i<ja[i]>a[j],这是逆序对,逆序对的数量加1

又由于归并排序中a数组的两个部分都是有序的,所以对于任意的i<=k<=middle都有a[k]>=a[i],由此有a[k]>=a[i]>a[j]

综上,逆序对有middle-i+1

ij取遍所有可取的值,逆序对的个数不重不漏,因此求和就是答案

然后证明最坏情况下的复杂度

由于是使用归并排序实现的,归并排序的复杂度为

$$
O(nlogn)
$$
显然得到结论
$$
\Theta(nlog{n})
$$
证明从略

下面给出算法的实现

import java.util.Scanner;

public class Main {

    static int length;
    static int[] dataArray;
    static int answer = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int caseNumber = in.nextInt();
        for (int caseIndex = 1; caseIndex <= caseNumber; caseIndex++) {
            length = in.nextInt();
            dataArray = new int[length];
            for (int i = 0; i < dataArray.length; i++) 
                dataArray[i] = in.nextInt();
            answer = 0;
            mergeSort(0, dataArray.length - 1);
            System.out.printf("Scenario #%d:\n%d\n\n", caseIndex, answer);
        }
    }

    private static void mergeSort(int leftEndPoint, int rightEndPoint) {
        if (leftEndPoint < rightEndPoint) {
            int middlePoint = (leftEndPoint + rightEndPoint) >>> 1;
            mergeSort(leftEndPoint, middlePoint);
            mergeSort(middlePoint + 1, rightEndPoint);
            merge(leftEndPoint, middlePoint, rightEndPoint);
        }
    }

    private static void merge(int leftEndPoint, int middlePoint, int rightEndPoint) {
        int leftCursor = leftEndPoint;
        int rightCursor = middlePoint + 1;
        int ancillaryCursor = leftEndPoint;
        int[] ancillaryArray = new int[dataArray.length];
        while (leftCursor <= middlePoint && rightCursor <= rightEndPoint) {
            if (dataArray[leftCursor] <= dataArray[rightCursor]) {
                ancillaryArray[ancillaryCursor] = dataArray[leftCursor];
                ++leftCursor;
            } else {
                answer += (middlePoint - leftCursor + 1); 
                // 核心代码就只有这一句,其他都是归并排序
                ancillaryArray[ancillaryCursor] = dataArray[rightCursor];
                ++rightCursor;
            }
            ++ancillaryCursor;
        }
        while (leftCursor <= middlePoint) {
            ancillaryArray[ancillaryCursor] = dataArray[leftCursor];
            ++leftCursor;
            ++ancillaryCursor;
        }
        while (rightCursor <= rightEndPoint) {
            ancillaryArray[ancillaryCursor] = dataArray[rightCursor];
            ++rightCursor;
            ++ancillaryCursor;
        }
        for (int i = leftEndPoint; i <= rightEndPoint; ++i) 
            dataArray[i] = ancillaryArray[i];
    }
}

以下列出部分测试数据

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0
Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

Exercises 3.2-3

证明

$$\log(n!)=\Theta(n\log n)$$

首先证明$$\log(n!)=\Omega(n\log n)$$
$$
\begin{align}
\log(n!) &=\sum^n_{k=1}\log{k} \\
& \geq \int^n_{1} \log {x} dx \\
& = n*(\ln{n} – 1) + 1 \\
& = n\ln{n} -n +1 \\
&= \log {e(n\ln{n}-n+1)} \\
&= \Omega(n \log{n})
\end{align}
$$

再证明$$\log(n!)=O(n\log n)$$
$$
\begin{align}
\log(n!) &=\sum^n_{k=1}\log{k} \\
& \leq \int^{n+1}_{2} \log {x} dx \\
&= (\ln{(n + 1)} – 1) \cdot (n + 1) – \log(4) + 2 \\
&= O(n \log{n})
\end{align}
$$

证明

$$n!=\omega(2^n)$$

对任意正常量$$c>0$$,都存在常量$$n_0>0$$,使得对所有的$$n\geq n_0$$,有$$0\leq c \cdot 2^n \lt n!$$成立

$$0\le c \cdot 2^n$$显然成立

关键在于$$c \cdot 2^n \lt n!$$

当$$c=1$$时由放缩法显然得知,取$$n_0$$为$$4$$,即$$n\ge4$$时有$$2^n \lt n!$$

同样放缩,直接放大到$$4 \cdot c $$,就可以看到上式恒成立

于是$$n!=\omega(2^n)$$

证明

$$n!=o(n^n)$$

对任意正常量$$c>0$$,都存在常量$$n_0>0$$,使得对所有的$$n\geq n_0$$,有$$0\leq n! \lt c \cdot n^n$$成立

$$c \ge1$$时
$$
\begin{align}
n(n-1)(n-2)…2\times1=n! & <n^n=n\times n\times n\times …\times n \\
&< c \cdot n^n (c \ge1 )
\end{align}
$$
对于任意的$$n$$显然成立

下面考虑$$0\lt c\lt1$$

$$
\begin{align}
\frac{n!}{n^n}&\gt 0 显然成立\\
\frac{\frac{(n+1)!}{(n+1)^{n+1}}}{\frac{n!}{n^n}}&\lt 1显然成立\\
\frac{(n+1)!}{(n+1)^{n+1}}&=\frac{n!}{n^n}\times[\frac{n}{n+1}]^n\\&=\frac{n!}{n^n}\times\frac{1}{(1+\frac{1}{n})^n}\\
\lim_{n \to + \infty}\frac{(n+1)!}{(n+1)^{n+1}}&=\lim_{n \to + \infty}\frac{n!}{n^n}\times\lim_{n \to + \infty}\frac{1}{(1+\frac{1}{n})^n}\\
记\lim_{n \to + \infty}\frac{(n+1)!}{(n+1)^{n+1}}&=\lim_{n \to + \infty}\frac{n!}{n^n}=X \\
则X&=X\cdot e\\
于是X& = 0 \\
即\lim_{x \to + \infty}{\frac{n!}{n^n}} &= 0
\end{align}
$$

由$$\lim_{x \to + \infty}{\frac{n!}{n^n}} = 0$$有$$n!=o(n^n)j$$

严格证明如下:


0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定