时间复杂度表示法

时间复杂度全称为渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系.

大O表示法

先看一段代码

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

从CPU角度来看,这些代码都是读数据运算写数据 ,这里把每一行代码运行时间都记为unit_time;
1. 第一行和第二行运行时间分别都是1个unit_time
2. 第四行和第五行运行时间都为n个unit_time 这里记为2n个unit_time
3. 所以这段代码的运行时间为2n+2个unit_time
4. 可以看出来所有的代码的执行时间T(n)与每行代码执行的次数成正比
在看以下一段代码

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

这里每行代码运行时间单位还是unit_time
1. 第2,3,4行都是1一个unit_time,即3个unit_time
2. 5,6行分别都是n个unit_time,即2n个unit_time
3. 7,8行分别都是n个unit_time,即n²个unit_time
4. 最后得出结果是2n+2n²+3个unit_time
从这两段代码都是可以看出来,程序运行时间(T(n))的都是与执行的代码行数n成正比
得出来的公式为 T(n) = O(f(n))
1. T(n)表示代码执行的时间,n表示数据规模的大小,f(n)标识每行代码执行的次数总和;公式中的O表示代码的执行时间T(n)和f(n)表达式成正比
2. 第一个例子的结果为 T(n) = O(2n+2) 第二个例子结果为T(n) = O(2n²+2n+3),这个就是大O时间复杂度表示法,大O表示法并不能很精确的计算出代码真正的执行时间,只是能表示出来代码执行时间随着数据规模的增长而增长,所以也称为渐进时间复杂度,简称时间复杂度;
3. 公式中的低阶常量系数都不会左右T(n)的大小,所以这里只需要记录一个最大的数据量,以上的例子公式就可以简写为 1.T(n) = O(n) 2. T(n) = O(n²);

O(logn) O(nlogn)

for ;; {
	i++
	i *= 2
	if i > Count {
		break
	}	
}

O(m+n) O(m*n)

func cal(m int,n int ) int {
	sum := 0
	i := 0
	for ; i < m ; i++ {
		sum  += i
	}
	j := 0
	for ; j < n; j++ {
		sum += j
	}
	return sum
}

空间复杂度全称为渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系.