时间与空间复杂度

基础与数据结构

说明

用输入规模描述资源增长；下例求和遍历 n 项，时间 O(n)、额外空间 O(1)。

分析

先确定 n 表示什么，再统计循环或递归会执行多少次。示例只遍历一次切片，所以输入翻倍时工作量大致翻倍；累计变量只占固定空间。

图解推演

求和 n 个元素，每个元素做一次读取与加法，工作总量与 n 成正比；n 翻倍时操作数也翻倍。累计器和索引的数量不随 n 增长，所以额外空间 O(1)。若把每步累计值都保存下来，时间仍为 O(n)，额外空间却变为 O(n)。

查看图表代码

适用前提与边界

复杂度描述的是增长趋势，常数开销和真实输入分布仍会影响性能。

示例输入与调用

fmt.Println(Sum([]int{2, 3, 5}))

运行输出

10

完整 Go 示例

package main

import "fmt"

func Sum(a []int) int {
	s := 0
	for _, x := range a {
		s += x
	}
	return s
}

func main() {
	fmt.Println(Sum([]int{2, 3, 5}))
}