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

2019-07-24 636 words 2 minutes

Contents

时间复杂度

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

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

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

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

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

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)

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

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

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

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