大数据、Java EE 学习资料请关注 B 站:https://space.bilibili.com/204792350

数据结构与算法 - 时间/空间复杂分析(1)

简介

数据结构和算法是为了解决代码性能以及节省资源的问题,所以就需要一个方法来考量代码执行效率是否超标,是否占用太多存储空间

这个方法就是 复杂度分析,学习数据结构和算法离不开 复杂度分析

算法的复杂度包括:时间复杂度和空间复杂度,两者以时间复杂度相对重要,因为在 Web 开发中,常见的性能优化策略都是以空间换时间,例如缓存系统

#为什么需要分析复杂度? 分析代码的复杂度可以知道,代码执行效率、消耗资源,以便优化,写出更高质量的代码。

掌握了复杂度分析,在编写代码的,会不经意的估算自己写的代码是否“合格”,有一种一眼扫过,尽在掌握之中的感觉,并且不需要额外取付出时间,那么不划算吗?

大 O 表示法

先来看一段代码:

$sum = 0;
for ($i=0; $i < n; ++$i) {
	$sum =+ $i;
}

在不同的环境下执行,结果是不同的,所以我们假设每行代码执行时间为:time

那么 2、3 行代码都需要执行一次,就是 2*time4、5 行代码循环次数分别是 n,那么就是 2n*time,这段代码的执行时间就是:T(n) = (2+2n)\*time,从这里可以看出来,所有代码执行时间T(n) 与 每行代码执行次数 n 是成正比

大O表示法公式: T(n)=O(f(n))

  • T(n):所有代码执行时间
  • f(n):每行代码执行次数的总和
  • O:表示 T(n)f(n) 成正比
  • n:表示数据规模

所以上面的代码使用大 O 表示法来分析就是:T(n) = O(2+2n),它不表示具体执行时间,而是表示 代码执行时间随着数据规模增大的变化趋势,也叫 渐进时间复杂度,简称 时间复杂度

既然它是表示一种变化趋势,那么可以将公式中的低阶、系数、常量这三部分定量值忽略,因为它随着时间变化不会产生任何影响,只需要记录一个最大量级即可,那么上面那段代码的复杂度可以这样写:T(n) = O(n)

如何使用大O表示法分析?

有三种实用的方法:

  1. 只关注循环次数最多的一段代码
  2. 加法法则:总复杂度等于量级最大的那段代码复杂度
  3. 乘法法则:嵌套代码复杂度等于嵌套内外代码复杂度的乘积
  4. 多个数据规模相加

加法法则:总复杂度等于量级最大的那段代码复杂度

例子:

function count(){

	# exmple 1
	$sum1 = 0;
	for ($i=0; $i <= 100; ++$i) {
		$sum1 =+ $i;
	}

	# exmple 2
	$sum2 = 0;
	for ($i=0; $i < n; ++$i) {
		$sum2 =+ $i;
	}

	# exmple 3
	$sum3 = 0;
	for ($i=0; $i < n; $i++) {
		$sum3 += $i;
		for ($j=0; $j < n; $j++) {
			$sum3 += $j;
		}
	}
	return $sum1 + $sum2 + $sum3;
}

上面三个循环分别求 $sum1、$sum2、$sum3 的值

第一个循环的次数为常量,所以忽略不分析,第二个循环和第三个循环分别是:O(n)、O(n²),所以这三段代码中,量级最大的是第三个循环,所以作为函数的时间复杂度

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

具体代码:

function call() {
	for ($i=0; $i < $n; $i++) {
		$ret =+ f($i);
	}

	function f($n) {
		for ($i=0; $i < $n; $i++) {
			$sum =+ $i;
		} 
		return $sum;
	}

}

上面代码中,循环中嵌套循环,第 3 行代码执行的次数是 n,但是它同时调用了 f 函数,算上函数内的执行次数 n,所以时间复杂度是:T(n) = T1(n) * T2(n) = O(n*n) = O(n²)

多个数据规模相加

例如,一个代码段中有两个循环,循环的次数由两个参数决定,这就是两个数据规模,那么我们无法得知它们谁的量级大,所以需要将它们相加之后作为代码段的复杂度

function call($m,$n)
  for ($i=0; $i < $m; ++$i) {
    $sum_1 = $sum_1 + $i;
  }

  for ($i=0; $j < $n; ++$j) {
    $sum_2 = $sum_2 + $j;
  }

  return $sum_1 + $sum_2;
}

无法得知 mn 谁的量级大,所以记为:O(m+n)

常量的时间复杂度(按数量级递增):

常见的时间复杂度 - 来自极客时间

  1. 常量阶 O(1)
  2. 对数阶 O(logn)
  3. 线性阶 O(n)
  4. 线性对数阶 O(nlogn)
  5. 平方阶 O(n²)、立方阶 O(n³) ... K次方阶 O(n^k)
  6. 指数阶 O(2^n)
  7. 阶乘阶 O(n!)

O(1)

代码段中不包含循环语句、递归,那么时间复杂度都是 O(1)

O(logn)、O(nlogn) 最为常见,也是最难分析的一种复杂度。

一个简单的例子:

$i = 1;

while($i <= n){
	$i *= 2;
}

每次循环都乘于 2,当大于 n 时就停止循环,这样的增长趋势,变量 i 的取值是一个等比数列,所以这段代码的时间复杂度是:O(log₂n)

2等比数列 - 来自极客时间

上面的的对数底是 2,但是不管底是多少,时间复杂度都记为:O(logn)

对数之间是可以互相转换的,log₃n = log₃2 * log₂n 所以:O(log₃n) = O(C * log₂n) C=log₃2 是一个常量,忽略之后就成了:O(Cf(n)) = O(f(n)) 所以不管底是多少都统一记为:O(logn)

如果一段代码的时间复杂度是 O(logn),我们循环执行 n 遍,时间复杂度就是 O(nlogn) 了,比如,归并排序、快速排序的时间复杂度都是 O(nlogn)

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

function call() {
	$var = 1;
	$arr = [$n];
}

代码第二行申请了一个大小为 1 的空间存储变 var,因为是常量所以忽略。

第三行申请了一个大小为 n 的空间存储变量,所以整个代码段空间复杂度为:O(n)

常量的空间复杂度:

  • O(1)
  • O(n)
  • O(n²)

相关工具

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×