数据结构 - 时间复杂分析

前言

时间复杂度简单来说就是一种可以粗略估计一个函数或者算法的执行效率的方法。并且它是宿主平台无关的，能够对的程序或算法有一个大致的认识，让我们知道，比如在最坏的情况下程序的执行效率如何。

既然是计算执行效率那么为什么不进行性能基准测试来衡量呢，性能测试通过统计、监控，就能得到算法执行的时间和占用的内存大小。但是这种测试一般都是代码开发结束后。且有一定的局限性。

1. 非常依赖环境，在不同的环境中得到的结果也可以的天差地别。
2. 数据的格式和数据的体量也会影响到最后的结果。

大 O 表示法

大 O 时间复杂度实并不表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

func sum(n int) int {
	sum := 0
	for i := 1; i <= n; i++ {
		sum += i
	}
	return sum
}

假设每行代码的执行时间都是一样的。为 time，那么第 2 行就需要 1 个 time，第3、4行会执行 n 次，所以耗时就是 2n*time，整个 sum 函数执行时间就等于 (1+2n)*time，整个代码执行时间T(n) 是与每行代码的执行次数f(n)成正比的。

如果用大 O 表示发来表示。那么 T(n)=O(f(n))。T(n) 是代码总的执行时间。n表示数据规模大小，f(n)表示每行代码执行的次数总和，公式中的 O 可以理解为执行每行代码的平均时间。(1+2n)*time 就等价于 O(2n+1)

时间复杂度分析

只关注循环执行次数最多的一段代码

大 O 这种复杂度表示方法只是表示一种变化趋势，在分析一段代码的时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

func sum(n int) int {
	println(n)
	sum := 0
	for i := 1; i <= n; i++ {
			sum += i
	}
	return sum
}

2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

func sum(n int) int {
	for i := 1; i <= n; i++ {
		sum1(i)
	}
	return 1
}

func sum1(n int) {
	for i := 1; i <= n; i++ {
		println(i)
	}
}

单看 sum 它的时间复杂度是O(n)，但是 sum1 的时间复杂度也是O(n)，所以整个sum 函数的时间复杂度就是 T(n)=T1(n) * T2(n)=O(n*n) =O(n^2)

总复杂度等于量级最大的那段代码的复杂度

总的时间复杂度就等于量级最大的那段代码的时间复杂度

func sum(n int) int {
	println(n)
	sum := 0
	for i := 1; i <= n; i++ {
		println(i)
	}

	for i := 1; i <= 1000; i++ {
		println(i)
	}

	for i := 1; i <= n; i++ {
		println(i)
		for j := 1; i <= n; j++ {
			println(j)
		}
	}

	return sum
}

1. 第一个循环的时间复杂度是O(n)。
2. 第二个循环属于常量执行，跟 n 无关，尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，都可以忽略掉。因为它本身对增长趋势并没有影响。
3. 第三段循环因为有嵌套，第 12、13行执行了n次，第 14、15行执行了n^2 次，取其最大的，所以它的复杂度是O(n^2)，整段代码也取复杂度最大的，所以也是O(n^2)。

常见时间复杂度

复杂度量级可以分为多项式和非多项式。

1. 由数和字母的积组成的代数式叫做非多项式，单独的一个数或一个字母也叫做非多项式。非多项式量级只有两个：O(2^n) 和 O(n!)，
2. 由若干个单项式相加组成的代数式叫做多项式

越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

O(1) - 常量

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。

func find(n []int, index int) int {
	println(index)
	return n[index]
}

这段代码，不管 n 的长度是10w还是100w，他的时间复杂度都是O(1)， 只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度都记作 O(1)。

O(logn)、O(nlogn) - 对数

func logn(n int) {
	i := 1
	for i < n {
		i *= 2
	}
}

每循环一次，i就乘于2， 执行x次，就有x个2相乘， 即2的x次方 当2的x次方大于n时，结束循环 所以，要求2^x=n，也就是 x=log2n，这段代码的时间复杂度就是 O(log2n)。

把O(logn)的代码循环执行n遍，时间复杂度就是O(nlogn)了

O(N) - 线性

随着 n 的增加，复杂度也会随之增加。

func sum(n int) int {
	sum := 0
	for i := 1; i <= n; i++ {
		sum += i
	}
	return sum
}

O(2^n) - 指数

当数据n增长时，整体的执行效率会增加n的平方，简单一点就是嵌套循环，比如冒泡排序，就是典型的O(n^2)，对n个数排序，需要扫描n*n次。

func sort(arr it) {
	for i := 0; i < len(*arr)-1; i++ {
		for j := 0; j < len(*arr)-1-i; j++ {
			temp := 0
			if (*arr)[j] > (*arr)[j+1] {
				temp = (*arr)[j]
				(*arr)[j] = (*arr)[j+1]
				(*arr)[j+1] = temp
			}
		}
	}
}

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

func slice(n int) {
	slice := make([]int, n)
	for i := 1; i <= n; i++ {
		println(i)
	}
}

第 2 行申请了一个长度为n的切片，剩下的代码没有申请内存的操作，所以整段代码的空间复杂度就是 O(n)。常见的空间复杂度就是 O(1)、O(n)、O(n2 )，空间复杂度分析比时间复杂度分析要简单很多规则也大部分是通用的。

总结

以上出自学习王争大佬的《数据结构与算法之美》课程学习笔记和自己的一些总结。