基本概念
算法复杂度的定义
算法复杂度是衡量算法执行效率的度量，主要关注：
- 时间复杂度：算法执行所需时间与数据规模的关系
- 空间复杂度：算法执行所需内存空间与数据规模的关系 link
算法分析的目标
- 预测算法在不同输入规模下的性能
- 比较不同算法的效率
- 识别算法的瓶颈
- 指导算法优化
渐进符号与表示法
大O符号（O）
表示算法的上界，描述最坏情况或增长的上限。
// O(n) 示例 - 线性查找
func linearSearch(arr []int, target int) int {
for i, v := range arr {
if v == target {
return i
}
}
return -1
}大Ω符号（Omega）
表示算法的下界，描述最好情况或增长的下限。
// Ω(1) 示例 - 线性查找的最好情况
func linearSearchBestCase(arr []int, target int) int {
// 当目标值在数组第一位时，为 Ω(1)
if len(arr) > 0 && arr[0] == target {
return 0
}
// ...其余代码
return -1
}大Θ符号（Theta）
表示算法的紧确界，同时描述上界和下界，即渐近精确的增长率。
// Θ(n) 示例 - 计算数组和
func sumArray(arr []int) int {
sum := 0
for _, v := range arr {
sum += v
}
return sum
}小o符号和小ω符号
- 小o：比O更严格的上界（严格小于）
- 小ω：比Ω更严格的下界（严格大于）
常见时间复杂度类别
常数时间 O(1)
执行时间与输入规模无关。
// O(1) 示例
func getFirstElement(arr []int) (int, error) {
if len(arr) == 0 {
return 0, fmt.Errorf("empty array")
}
return arr[0], nil
}对数时间 O(log n)
每一步都将问题规模缩小为原来的一部分（通常是一半）。
// O(log n) 示例 - 二分查找
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := (left + right) / 2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}线性时间 O(n)
执行时间与输入规模成正比。
// O(n) 示例
func findMax(arr []int) int {
if len(arr) == 0 {
return 0
}
max := arr[0]
for _, v := range arr[1:] {
if v > max {
max = v
}
}
return max
}线性对数时间 O(n log n)
多数高效排序算法的时间复杂度。
// O(n log n) 示例 - 归并排序
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 merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
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
}平方时间 O(n²)
嵌套循环的典型复杂度。
// O(n²) 示例 - 冒泡排序
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}指数时间 O(2^n)
问题规模每增加一个单位，运行时间就翻倍。
// O(2^n) 示例 - 递归计算斐波那契数列
func fibonacciRecursive(n int) int {
if n <= 1 {
return n
}
return fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
}阶乘时间 O(n!)
全排列问题的典型复杂度。
// O(n!) 示例 - 计算全排列
func permutations(arr []int) [][]int {
var result [][]int
generatePermutations(arr, 0, &result)
return result
}
func generatePermutations(arr []int, start int, result *[][]int) {
if start == len(arr)-1 {
temp := make([]int, len(arr))
copy(temp, arr)
*result = append(*result, temp)
return
}
for i := start; i < len(arr); i++ {
// 交换元素
arr[start], arr[i] = arr[i], arr[start]
// 递归生成
generatePermutations(arr, start+1, result)
// 回溯
arr[start], arr[i] = arr[i], arr[start]
}
}空间复杂度
常见空间复杂度
- O(1)：常数空间
- O(log n)：对数空间
- O(n)：线性空间
- O(n²)：平方空间
空间复杂度分析示例
// O(n) 空间复杂度示例
func createCopy(arr []int) []int {
copy := make([]int, len(arr))
for i, v := range arr {
copy[i] = v
}
return copy
}
// O(1) 空间复杂度示例 - 原地操作
func reverseInPlace(arr []int) {
for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
arr[i], arr[j] = arr[j], arr[i]
}
}复杂度分析方法
迭代分析
通过计算循环次数确定时间复杂度。
// 两层循环，O(n²)
func iterativeSolution(n int) int {
result := 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
result += i * j
}
}
return result
}递归分析
通过递归关系式和主定理确定递归算法的复杂度。
递归关系式：T(n) = aT(n/b) + f(n)
- a：子问题数量
- b：子问题规模缩减因子
- f(n)：分解和合并的代价
// T(n) = 2T(n/2) + O(n)，整体复杂度为O(n log n)
func recursiveSolution(arr []int, left, right int) int {
if left == right {
return arr[left]
}
mid := (left + right) / 2
leftSum := recursiveSolution(arr, left, mid)
rightSum := recursiveSolution(arr, mid+1, right)
// 合并操作 O(n)
crossSum := calculateCrossSum(arr, left, mid, right)
return max(leftSum, rightSum, crossSum)
}均摊分析
针对一系列操作的平均性能，特别适用于动态数据结构。
// 动态数组扩容，均摊O(1)
type DynamicArray struct {
items []int
size int
capacity int
}
func (da *DynamicArray) Add(item int) {
if da.size == da.capacity {
// 扩容操作，成本O(n)但均摊后为O(1)
da.capacity *= 2
newItems := make([]int, da.capacity)
copy(newItems, da.items)
da.items = newItems
}
da.items[da.size] = item
da.size++
}特殊复杂度分析
最好情况、最坏情况与平均情况
// 不同情况的复杂度
func quickSort(arr []int, left, right int) {
if left < right {
// 最好情况：O(n log n) - 每次都平衡分割
// 最坏情况：O(n²) - 每次都不平衡（如已排序数组）
// 平均情况：O(n log n)
pivot := partition(arr, left, right)
quickSort(arr, left, pivot-1)
quickSort(arr, pivot+1, right)
}
}
func partition(arr []int, left, right int) int {
pivot := arr[right]
i := left - 1
for j := left; j < right; j++ {
if arr[j] <= pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[right] = arr[right], arr[i+1]
return i + 1
}均摊时间复杂度
适用于少数操作耗时较多，但总体影响有限的情况。
// 双栈实现队列（Push均摊O(1)，Pop均摊O(1)）
type Queue struct {
inStack, outStack []int
}
func (q *Queue) Push(x int) {
q.inStack = append(q.inStack, x) // O(1)
}
func (q *Queue) Pop() int {
if len(q.outStack) == 0 {
// 将inStack元素全部移到outStack，O(n)操作
// 但均摊后每个元素只移动一次，所以均摊O(1)
for len(q.inStack) > 0 {
q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
q.inStack = q.inStack[:len(q.inStack)-1]
}
}
x := q.outStack[len(q.outStack)-1]
q.outStack = q.outStack[:len(q.outStack)-1]
return x
}在线算法与离线算法
// 在线算法示例 - 移动平均值
type MovingAverage struct {
size int
sum int
queue []int
}
func NewMovingAverage(size int) *MovingAverage {
return &MovingAverage{
size: size,
sum: 0,
queue: make([]int, 0, size),
}
}
// O(1) 时间复杂度，实时处理每个新值
func (ma *MovingAverage) Next(val int) float64 {
ma.sum += val
ma.queue = append(ma.queue, val)
// 如果窗口已满，移除最旧的元素
if len(ma.queue) > ma.size {
ma.sum -= ma.queue[0]
ma.queue = ma.queue[1:]
}
return float64(ma.sum) / float64(len(ma.queue))
}算法复杂度比较
常见复杂度对比
从快到慢排序：
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
不同复杂度算法随输入规模的增长速率
| 输入规模 n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2^n) | O(n!) |
|---|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 30 | 100 | 1024 | 3.6×10⁶ |
| 100 | 1 | 7 | 100 | 700 | 10⁴ | 10³⁰ | 10¹⁵⁸ |
| 1000 | 1 | 10 | 10³ | 10⁴ | 10⁶ | 10³⁰⁰ | 10²⁵⁶⁷ |
选择合适的算法
func chooseAlgorithm(arr []int, isOrdered bool) {
n := len(arr)
switch {
case n <= 10:
// 小数据集，使用简单但可能较慢的算法
bubbleSort(arr) // O(n²)
case isOrdered:
// 对于已排序或接近排序的数组
insertionSort(arr) // 最好O(n)，最坏O(n²)
case n <= 1000:
// 中等大小数据集
quickSort(arr, 0, n-1) // 平均O(n log n)
default:
// 大数据集
mergeSort(arr) // 稳定O(n log n)
}
}高级复杂度概念
NP完全性
NP完全问题：目前没有已知的多项式时间算法，但可以在多项式时间内验证解的正确性。
// NP完全问题示例 - 子集和问题
func isSubsetSumPossible(arr []int, target int) bool {
n := len(arr)
dp := make([][]bool, n+1)
for i := range dp {
dp[i] = make([]bool, target+1)
}
// 初始化：空集可以得到和为0
for i := 0; i <= n; i++ {
dp[i][0] = true
}
// 动态规划
for i := 1; i <= n; i++ {
for j := 1; j <= target; j++ {
if j < arr[i-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i-1]]
}
}
}
return dp[n][target]
}近似算法
// 近似算法示例 - 贪心解决背包问题
type Item struct {
weight int
value int
}
func fractionalKnapsack(items []Item, capacity int) float64 {
// 按价值密度（value/weight）排序
sort.Slice(items, func(i, j int) bool {
return float64(items[i].value)/float64(items[i].weight) >
float64(items[j].value)/float64(items[j].weight)
})
totalValue := 0.0
currentWeight := 0
for _, item := range items {
if currentWeight+item.weight <= capacity {
// 整个物品都能装下
currentWeight += item.weight
totalValue += float64(item.value)
} else {
// 只能装部分
remainingCapacity := capacity - currentWeight
totalValue += float64(item.value) * float64(remainingCapacity) / float64(item.weight)
break
}
}
return totalValue
}并行算法复杂度
// 并行算法示例 - 并行归并排序
func parallelMergeSort(arr []int, threshold int) []int {
if len(arr) <= threshold {
// 小数组使用普通归并排序
return mergeSort(arr)
}
mid := len(arr) / 2
// 创建两个通道接收结果
leftChan := make(chan []int)
rightChan := make(chan []int)
// 并行排序两半
go func() {
leftChan <- parallelMergeSort(arr[:mid], threshold)
}()
go func() {
rightChan <- parallelMergeSort(arr[mid:], threshold)
}()
// 接收结果并合并
left := <-leftChan
right := <-rightChan
return merge(left, right)
}总结与进阶
算法复杂度分析的核心原则
- 关注增长率，忽略常数和低阶项
- 识别关键操作和主导因素
- 考虑最坏情况、平均情况和最好情况
- 理解空间与时间的权衡
进阶
- 分布式算法复杂度
- 并行计算模型
- 量子计算复杂度
- 随机化算法复杂度
- 近似算法与参数化复杂度