数据结构与算法之时间、空间复杂度

算法中最最最基础的概念,总结一下

时间复杂度

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

大 O 表示法

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

常见时间复杂度

O(1) 常数阶

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

O(logn) 对数阶

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

O(n) 线性阶

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

O(nlogn) nlogn 阶

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

O(n^2) 平方阶

1def ON2(num):
2  total = 0
3  for i in range(num):
4    for j in range(num):
5      total += i+j
6  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) 常数阶

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

O(n) 线性阶

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

如何计算

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

最坏情况与平均情况

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

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

  • 时间和空间复杂度只能二选一
  • 牺牲时间换空间
  • 牺牲空间换时间
  • 通常是优先选择时间复杂度更好的
Licensed under CC BY-NC-SA 4.0