这周调整了下计划,鉴于很多不懂的知识需要大量的时间去消化及整理输出,因此,改为每逢节假日更新每日一问。
今天来整理算法复杂度的相关知识。在算法中包含两种复杂度,一种是时间复杂度,另一种是空间复杂度。这篇文章主要总结 时间复杂度 相关的知识点。
在时间频度 T(n) 中,n 又代表着问题的规模,当 n 不断变化时,T(n) 也会不断地随之变化。为了了解这个变化的规律,时间复杂度这一概念就被引入了。一般情况下算法基础操作的重复执行次数为问题规模 n 的某个函数,也就是时间频度 T(n)。如果有某个辅助函数 f(n),当趋于无穷大的时候,T(n)/f(n) 的极限值是不为零的某个常数,那么 f(n) 是 T(n) 的同数量级函数,记作 T(n)=O(f(n)),被称为算法的渐进时间复杂度,又简称为时间复杂度。- 算法(一)时间复杂度[1]
在计算机科学领域,会用大 O 符号或者说大 O 表示法来度量一个算法的时间复杂度。那什么是大 O 表示法呢?
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others collectively called Bachmann–Landau notation or asymptotic notation. 大 O 表示法是一种数学符号,用于描述当参数趋向于特定值或无穷大时函数的限制行为。它是 Paul Bachmann,Edmund Landau 等人发明的一系列符号的之一,统称为巴赫曼 - 兰道符号或渐近符号。- 维基百科[4]
因为时间复杂度为 T(n)=O(f(n)),有个趋近函数 O(),所以被称为大 O 表示法。现在假设一个列表包含 n 个元素。我们用简单查找的话,需要遍历检查每一个元素,因此需要执行 n 次操作。使用大 O 表示法,其运行时间为 O(n),f(n) = n 为操作数。这里需要注意的是,大 O 表示法是没有单位的,它指的并不是以秒为单位的运行时间。大 O 表示法能够用来比较操作数,通常它指的是算法运行时间的增速。比如,为检查长度为 8 的列表,用简单查找法的时间复杂度是 O(f(n)),f(n) = 8;如果用二分查找的话,时间复杂度是 O(f(n)),f(n) = log2 8 = 3。从计算结果上看来,几乎快了 3 倍。
还有一点需要注意的是,大 O 表示法描述的始终是最坏的情况。
常见的一些大 O 运行时间有以下几种:
知道了大 O 表示法,那么实际的时间复杂度要怎么计算呢?下面举几个例子来说明。
O(1):描述了一个算法不管输入的大小是多少,其时间复杂度永远为常数(不变)。比如,下方的例子,判断一个字符串 list 的首个元素是否为空。因为无论输入的 list 有多长,都只判断首字符是否为空,执行次数为 1,所以时间复杂度为 O(1)。
def isFirstElementNull(str_list):
rerurn str_list[0] == ''
O(n):描述了一个算法的时间复杂度将随着算法输入的增加而线性增加。比如,下面的算法,判断一个字符串 list 是否包含某些子字符串值。虽然算法可能会很早的就停止循环,并不完全执行所有的迭代,但需记得大 O 表示法描述的是最坏的情况。如果一个算法最大迭代 n 次,那么其时间复杂度就是 O(n)。所以,下面函数的时间复杂度为 O(n)。
def isContainValue(str_list, value):
for i in str_list:
if i == value:
return True
else:
return False
O(n2):描述了一种算法,其时间复杂度与输入数据集的大小的平方成正比。这在涉及数据集的嵌套迭代的算法中很常见。更深的嵌套迭代将会有 O(n3),O(n4) 等。比如,下面的代码是两层迭代,按照最坏的打算,迭代总次数为 ixj,是两个数的相乘,可以直接表示为 nxn,即 n 的平方。所以,时间复杂度可以表示为 O(n2)。
def isContainDuplicates(str_list):
for i in range(len(str_list)): # 最多迭代 i 次
for j in range(len(str_list): # 最多迭代 j 次
if i != j and str_list[i] = str_list[j]:
return True
return False
O(log2n):描述的是一种二分查找的时间复杂度。二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回 null 。比如,要猜测 1-100 中的一个数字。二分查找将每次迭代的数据集减半,直到找到该值,或者直到它不再分割数据集为止。 迭代中的数据集大小依次有 n,n/2,n/4,....,n/2k(k 为循环的次数)。因为最后结果 n/2k >= 1。如果令 n/2k = 1,将得到 k = log2n。所以,二分查找的时间复杂度为 O(log2n)。
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high :
mid = (low + high) % 2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
[1]. 算法(一)时间复杂度 [2]. 算法图解 - Aditya Bhargava [3]. A beginner's guide to Big O notation [4]. Big O notation - wikipedia [5]. Binary Search - 二分查找