一、时间复杂度

常见的时间复杂度

  • 常数级O(1)
  • 线性增长O(n)
  • 幂增长O(n²)
  • 对数增长O(logn)。
for i := 0; j < 2; i++ {
    num++
    num *= num
}

时间复杂度为f(n)=5

f(n)的计算方法是将每行代码执行时间都看作一个相同的时间单位,在这段代码中第一行执行了1次,第二行执行了2次,第三行执行了2次,因此f(n)=5,可以看出时间复杂度是不随n变化而变化的,也就是常数级时间复杂度为O(1)而不是线性的。

for i := 0; j < n; i++ {
    num++
    num *= num
}

时间复杂度为f(n)=2n+1

同样的分析方法,第一行执行了一个时间单位,第二行执行了n个时间单位,第三行执行了n个时间单位,可以得出f(n)=2n+1。因为时间复杂度表示的是算法随n变化的一种趋势,而f(n)=2n+1表示的就是一种线性增长关系,为了统一表达忽略常数项和系数,可得时间复杂度为O(n)!

for i := 0; i < n; i++ {
  for j := 0; j < n; j++ {
    num++
    num *= num
  }
}

幂增长O(n²)显然就是两次对n的for循环。

二分查找算法

二分法的查找和二叉查找树的查找一样都是不断的折半剪枝达到优化的效果。以树的查找为例,从n个数中找到目标数target,假设有k层,每一层即为一次查找,一共有2ᴷ-1个节点,即2ᴷ -1=n,求得k为log(n-1),去掉常数项最终时间复杂度为O(logn)。

二、空间复杂度

num := 0
n := 1
res := num * n

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,程序在运行时,不会随着某个变量的值增大而增大,因此上述代码中的空间复杂度为o(1)

nums := make([]int, 0, n)

for i := 0; i < n; i++ {
    nums[i] = i
}

在这段代码中申请了一个额外的nums,他的大小随n的变化而变化,因此空间复杂度为O(n)

递归

递归的空间复杂度有一个计算公式递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度,因为递归压的是函数栈帧,而不是给每个节点都申请一片内存空间。因此无论F(n)当中的n有多大,当中的F都只占用了一块内存不会重复申请内存,假设一个F的空间为m,那么最终空间复杂度为O(n*m),去掉系数项最终空间复杂度为O(n)。