golang-cookbook

Appearance

intro ​

分治算法（Divide and Conquer）是一种将大问题分解为多个较小的子问题，独立求解后再合并其结果的算法策略。其基本思想是：分而治之，即通过递归将问题分解为更小的子问题，然后将解决子问题的结果合并起来，最终得到原问题的解。

分治算法的三大步骤： ​

  1. 分解：将问题分解成若干个规模较小的子问题。
  2. 解决：递归地解决这些子问题。
  3. 合并：将各子问题的解合并成原问题的解。

分治算法的经典示例 ​

常见的分治算法包括：

  • 归并排序（Merge Sort）
  • 快速排序（Quick Sort）
  • 二分查找（Binary Search）
  • 矩阵乘法（Strassen’s Matrix Multiplication）

1. 归并排序（Merge Sort） ​

归并排序是一种典型的分治算法，利用递归将数组分成更小的子数组，再将这些子数组合并成有序数组。

算法步骤： ​

  1. 将数组从中间分割成两半。
  2. 递归地对每个子数组进行归并排序。
  3. 合并两个已排序的子数组。

代码示例（Go）： ​

go
package main

import "fmt"

// 合并两个已排序的数组
func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

// 归并排序
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func main() {
    arr := []int{5, 3, 8, 4, 2, 7, 1, 6}
    sortedArr := mergeSort(arr)
    fmt.Println("Sorted Array:", sortedArr)
}

时间复杂度： ​

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)

2. 快速排序（Quick Sort） ​

快速排序通过一个"基准"（pivot）元素将数组分成两部分，再对这两部分递归排序。每一轮的排序通过将小于基准的元素放到左边，大于基准的元素放到右边来实现。

算法步骤： ​

  1. 从数组中选择一个基准元素。
  2. 将数组分成两部分：一部分包含比基准小的元素，另一部分包含比基准大的元素。
  3. 递归地对左右部分进行排序。
  4. 合并排序结果。

代码示例（Go）： ​

go
package main

import "fmt"

// 快速排序
func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[0]
    left, right := []int{}, []int{}
    for _, v := range arr[1:] {
        if v < pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    return append(append(quickSort(left), pivot), quickSort(right)...)
}

func main() {
    arr := []int{5, 3, 8, 4, 2, 7, 1, 6}
    sortedArr := quickSort(arr)
    fmt.Println("Sorted Array:", sortedArr)
}

时间复杂度： ​

  • 平均时间复杂度：O(n log n)
  • 最坏时间复杂度：O(n²)（当数组已经接近有序时）
  • 空间复杂度：O(log n)

3. 二分查找（Binary Search） ​

二分查找是一种在有序数组中查找元素的分治算法。每次通过比较目标值与中间值的大小来决定继续在左半部分还是右半部分查找。

算法步骤： ​

  1. 设定搜索区间的左右边界，通常是数组的起始和结束位置。
  2. 找到区间的中间位置，并与目标值进行比较。
  3. 如果目标值小于中间值，则继续在左半部分查找；如果目标值大于中间值，则继续在右半部分查找。
  4. 递归或迭代执行上述操作，直到找到目标元素或者区间为空。

代码示例（Go）： ​

go
package main

import "fmt"

// 二分查找
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // 未找到目标元素
}

func main() {
    arr := []int{1, 3, 5, 7, 9, 11, 13, 15}
    target := 7
    result := binarySearch(arr, target)
    if result != -1 {
        fmt.Println("Target found at index:", result)
    } else {
        fmt.Println("Target not found")
    }
}

时间复杂度： ​

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

4. 矩阵乘法（Strassen’s Matrix Multiplication） ​

Strassen 算法是一种改进的矩阵乘法算法，它将矩阵乘法从传统的 O(n³) 的时间复杂度降低到约 O(n².81) 的时间复杂度。通过将矩阵分解成更小的矩阵并利用递归来减少计算量。

算法步骤： ​

  1. 将矩阵分成 4 个子矩阵。
  2. 通过 7 次矩阵乘法和一些加法操作来获得最终结果。
  3. 递归地对子矩阵进行 Strassen 乘法。

代码示例： ​

Strassen 算法比较复杂，通常需要更多的数学推导和矩阵分解步骤。如果需要具体代码，可以参考一些开源实现。

时间复杂度： ​

  • 时间复杂度：O(n^2.81)
  • 空间复杂度：O(n²)

总结 ​

分治算法是许多高效算法的基础，其优势在于能够将复杂问题拆解成较小的问题，从而降低解决问题的复杂度。通过递归与合并步骤，分治算法在多个领域得到了广泛应用，如排序、搜索、图像处理、矩阵运算等。