时间复杂度

算法的执行时间与算法输入值之间的的关系,即算法的执行效率

大 O 表示法

  1. 用常数 1 取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是 1,则去除与这个项相乘的常数。得到的结果就是大 O 阶

常见时间复杂度

O(1) 常数阶

1
2
3
4
def O1(num):
  i = num
  j = num*2
  return i + j

O(logn) 对数阶

1
2
3
4
5
def OlogN(num):
	i = 1
  while (i < num):
    i = i * 2
  return i

O(n) 线性阶

1
2
3
4
5
def ON(num):
  total = 0
  for i in range(num):
    total += i
   return total

O(nlogn) nlogn 阶

1
2
3
4
5
6
7
8
def ONlogN(num):
	total = 0
	for i in range(num):
    j = 1
		while (j < num):
			total += i+j
			j = j * 2
	return total

O(n^2) 平方阶

1
2
3
4
5
6
def ON2(num):
	total = 0
  for i in range(num):
    for j in range(num):
			total += i+j
	return total

对比

常用时间复杂度所耗费的时间从小到大依次是:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n!) < O(n^n)

相关文档:Big-O Cheat Sheet

空间复杂度

算法的存储空间与输入值之间的关系,表示方法同样也为大 O 表示法

常见时间复杂度

O(1) 常数阶

1
2
3
4
5
def O1(num):
	total = 0
  for i in range(num):
    total += i
  return total

O(n) 线性阶

1
2
3
4
5
def ON(nums)
	array = []
  for num in nums:
    array.append(num)
  return array

如何计算

  • 变量:常量时为 O(1),数组、列表则可能是 O(n)、O(n^2)
  • 递归:递归栈 O(n)

最坏情况与平均情况

最坏情况运行时间是一种保证,那就是运行时间不会再长了。在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况的运行时间。平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。一般没有特殊说明的情况下,时间复杂度都是指最坏时间复杂度。

如何衡量时间 / 空间复杂度

  • 时间和空间复杂度只能二选一
  • 牺牲时间换空间
  • 牺牲空间换时间
  • 通常是优先选择时间复杂度更好的