目录
时间复杂度
-
执行次数函数 大O表示 阶 13 O(1) 常数阶 2n+3 O(n) 线性阶 3n²+2n+1 O(n2) 平方阶 5log2n+20 O(logn) 对数阶 2n+3nlog2n+19 O(nlogn) nlogn阶 6n3+2n2+3n+4 O(n3) 立方阶 2n O(2n) 指数阶 -
-
# 第一组 print('Hello,World') print('Hello,Python') print('Hello,Java') # 第二组 for i in range(n): print('Hello,World') for j in range(n): print('Hello,World')
在第一组代码中,有三行代码,共执行了3次,所以它的运行时间为O(3×t);
第二组代码中,第一个for循环中执行了print,所以执行时间为n×t,在嵌套的for循环中,执行了n次,所以运行时间为n²×t,所以第二组代码运行时间为O((n+n²)×t)。
空间复杂度
-
空间复杂度是用来评估算法内存占用大小的式子。空间复杂度的表示方式与时间复杂度完全一样。示例代码如下:
# 第一组 a='11' #变量 b='22' c='33' # 第二组 a=[1,2,3,,...,n] # 一维数组 # 第三组 a[m][n]=9 # 二维数组
在第一组代码中,有a、b、c三个变量,所以其空间复杂度为O(1);
第二组代码中,a是一维数组,长度为n,所以其空间复杂度为O(n);
第三组代码中,a是二维数组,长度mn,所以其空间复杂度为O(mn);
注意:一般情况下,时间复杂度的优先级比空间复杂度优先级高,也就是优先选择时间复杂度低的算法。