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

4月3日 · 2018年

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

### Problems 2-4

#### a

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

#### b

$$(n-1)+(n-2)+…+2+1$$

$$\frac{n(n-1)}{2}$$

#### d

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

$$O(nlogn)$$

$$\Theta(nlog{n})$$

import java.util.Scanner;

public class Main {

static int length;
static int[] dataArray;

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();
mergeSort(0, dataArray.length - 1);
}
}

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)$$

\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}

\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)$$

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

#### 证明

$$n!=o(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}

\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}

0 条回应