分而治之

本文是 Design and Analysis of Algorithms 的一部分

每天大清早是真的起不来床
这课的 Kahoot 我是一分也没拿到

Inversion Count

定义

给定一个数组 $A$，如果 $i < j$ 且 $A[i] > A[j]$，则称 $(i, j)$ 是 $A$ 的一个逆序对

也就是说，某个前面的元素比后面的元素大，这样的对数就是逆序对

如有 arr[] = [8, 4 ,2, 1]
则逆序对为 (8, 4), (8, 2), (8, 1), (4, 2), (4, 1), (2, 1)
共 6 对

简单解法

1. 遍历数组
2. 对于元素 $A[i]$，遍历 $A[i+1:]$，统计比 $A[i]$ 小的元素个数
3. 累加

const arr = [8, 4, 2, 1];
let count = 0;

for (let i = 0; i < arr.length; i++) {
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[i] > arr[j]) {
      count++;
    }
  }
}

console.log(count); // 6

$O(n^2)$

Merge Sort

首先复习一下 归并排序

MergeSortInversion(A, low, high) {
  if (low < high) {
    mid := (low + high) / 2

    leftCount := MergeSortInversion(A, low, mid)
    rightCount := MergeSortInversion(A, mid + 1, high)

    mergeCount := Merge(A, low, mid, high)

    return leftCount + rightCount + mergeCount
  }
}

Merge(A, low, mid, high) {
  leftIndex := low
  rightIndex := mid + 1
  arrayIndex := low

  inversionCount := 0
  tempArray := []

  while (leftIndex <= mid && rightIndex <= high) {
    if (A[leftIndex] <= A[rightIndex]) {
      tempArray[arrayIndex] = A[leftIndex]
      leftIndex++
    } else {
      tempArray[arrayIndex] = A[rightIndex]
      rightIndex++
      inversionCount += mid - leftIndex + 1
    }
    arrayIndex++
  }

  while (leftIndex <= mid) {
    tempArray[arrayIndex] = A[leftIndex]
    leftIndex++
    arrayIndex++
  }

  while (rightIndex <= high) {
    tempArray[arrayIndex] = A[rightIndex]
    rightIndex++
    arrayIndex++
  }

  for (i := low; i <= high; i++) {
    A[i] = tempArray[i]
  }

  return inversionCount
}

时间复杂度为 $O(n \log{n})$

Max Increasing

给定一个数组 $A$，找到一对 $(i, j)$ 有 $1 \leq i \leq j \leq n$ 使得 $A[j] - A[i]$ 最大

通常找最大差值的问题使用 $O(n)$ 的算法解决，不过这里要求分治法所以

FindMaxDiff(A, low = 0, high = len(A) - 1) {
  if (low >= high)
    return 0

  mid := (low + high) / 2

  leftMaxDiff := FindMaxDiff(A, low, mid)
  rightMaxDiff := FindMaxDiff(A, mid + 1, high)

  leftMin := FindMin(A, low, mid)
  rightMax := FindMax(A, mid + 1, high)
  crossMaxDiff := rightMax - leftMin

  return Math.max(leftMaxDiff, rightMaxDiff, crossMaxDiff)
}

第 $k$ 大

Given different real numbers an array A[1:n] and an integer $1 \leq k \leq n$.
Let’s determine the $k$-th biggest element of the array.
The cost of the procedure should be $O(n \log{n})$.

快速选择

其实就是快排中轴值计算的过程，时间复杂度为 $O(n)$

QuickSelect(A, low = 1, high = n, k) {
  if (low = high)
    return A[low]

  pivotIndex := Partition(A, low, high)
  position := pivotIndex - low + 1

  if (k = position)
    return A[pivotIndex]
  else if (position > k)
    return QuickSelect(A, low, pivotIndex - 1, k)
  else
    return QuickSelect(A, pivotIndex + 1, high, k - position)
}

Partition(A, low, high) {
  pivot := A[high]
  i := low - 1

  for (j := low; j < high; j++) {
    if (A[j] <= pivot) {
      i++
      Swap(A[i], A[j])
    }
  }

  Swap(A[i + 1], A[high])

  return i + 1
}

但其实如果要达到 $\theta(n \log{n})$ 的话直接快速排序然后取第 $k$ 个元素就好了