# Karatsuba Multiplication

A method for multiplying two integers.

## 原理

x=10^{n / 2} \cdot a+b \ y=10^{n / 2} \cdot c+d \ \begin{align} x \cdot y &=\left(10^{n / 2} \cdot a+b\right) \cdot\left(10^{n / 2} \cdot c+d\right) \ &=10^{n} \cdot(a \cdot c)+10^{n / 2} \cdot(a \cdot d+b \cdot c)+b \cdot d \tag{3}\label{eq3} \end{align}
$n​$ 是数字位数。

key trick：$a · d + b · c$ 可以写成
$$\underbrace{(a+b) \cdot(c+d)}_{=a \cdot c+a \cdot d+b \cdot c+b \cdot d}-a \cdot c-b \cdot d=a \cdot d+b \cdot c$$

1. Recursively compute $a · c$.
2. Recursively compute $b · d$.
3. Compute $a + b$ and $c + d$ (using grade-school addition), and recursively compute $(a + b) \cdot (c + d)$.
4. Subtract the results of the first two steps from the result of the third step to obtain $a · d + b · c$.
5. Compute $\eqref{eq3}$ by adding up the results of steps 1, 2, and 4, after adding $10^n$ trailing zeroes to the answer in step 1 and $10^{n/2}$ trailing zeroes to the answer in step 4.

# Merge Sort

## Running Time of MergeSort)

For every input array of length $n \geq 1$, the MergeSort algorithm performs at most
$$6nlog_{2}n+6n$$
operations, where $log_2$ denotes the base-2 logarithm.

# Counting Inversions in $O(n log n)$ Time

A Divide-and-Conquer Approach.

• Input:

An array A of distinct integers.

• Output:

The number of inversions of A—the number of pairs $(i, j)$ of array indices with $i < j$ and $A[i] > A[j]$.

## Pseudocode

Let’s classify the inversions $(i, j)$ of an array A of length n into one of three types:

• left inversion: an inversion with $i, j$ both in the first half of the array (i.e., $i, j \le \frac{n}{2}$);
• right inversion: right inversion: an inversion with $i, j$ both in the second half of the array (i.e., $i, j \gt \frac{n}{2}$);
• split inversion: an inversion with $i$ in the left half and $j$ in the right half (i.e., $i \le n2 \lt j$).

example:

## 实现

• 第二周编程作业:

注意要考虑 CD 提前遍历完的特殊情况。

# Quick Sort

## Pseudocode

In-Place Implementation:

## 实现

﻿
----------over----------
﻿