LeetCode学习笔记- 写程式非常重要的概念- 时间复杂度与空间复杂度

Github连结

1. 时间复杂度与空间复杂度是什么

时间复杂度Time Complexity

• 为一个函式，定性描述了演算法执行所需的时间
• 常用Big-O符号(ex. O())来表示，只考虑函式的最高项，而不考虑包含这个函式的系数

空间复杂度Space Complexity

• 演算法计算过程中所消耗的内存空间
• 常用Big-O符号(ex. O())来表示

Big-O 符号(Big O notation)

• 或称为渐近符号，描述渐近行为的数学符号
• 使用另一个函式来说明函式数量级的渐近上界，也就是函式中的最高项
• 在Computer Science中，用在分析演算法复杂度上，也就是描述演算法复杂度的执行效率
• 它只会显示演算法执行函式的最大指数、最高次方项或是常数(1)

举例: 执行的演算法如果是6x^2+2x+8，那它会表示为O(n^2)

观念:为什么Big-O不表示为完整的函式呢?

拿前面的例子最高项系数6要被省略来说明，当n很大的时候，系数就显得很小，也就是系数的影响力根本为不足道，同理其它项跟常数也是，所以决定复杂度的通常就是最高项而已

2. 为什么需要知道时间复杂度与空间复杂度?

疑惑

当然之前有教过大家使用%timeit来计算一下执行时间不就好了? 干嘛这么麻烦呢? 但是大家可能会发现每次重新计算执行时间都会有点不同，更不用说换台电脑试试了，每台电脑的效能并不一样，执行同一段程式，有的电脑快，有的电脑慢，所以当然不能只凭这个方法去决定演算法写的好坏

答案

两位工程师写的程式都是做到同一件事，但是为什么只有一个被人家说比较高端呢xd 我们要怎么去评断一位工程师程式写的好坏呢? 当然就要透过时间复杂度与空间复杂度了喔，这样我们就能了解到执行这个演算法，我们的执行效率跟空间的利用度

3. 实作: 计算时间与空间复杂度

• 范例一

def example_1(x):
  total = 0
  for i in range(x):
    total += i*i
  return total
example_1(10)

时间复杂度

一个for回圈去执行x次，经过回圈计算后做了x次的加法和x次的乘法，所以函式的时间复杂度为O(n)

空间复杂度

使用了一个变数total，和一个变数i，函式不会因为x变大了，需要多宣告变数，所以空间复杂度为O(1)

• 范例二

def example_2(x):
  total = 0
  for i in range(x):
    if i > 6:
      break
    else:
      total += i * i
  return total
example_2(10)

时间复杂度

不管x多大只要超过第七次，程式就会break，因为不会随着x改变，所以时间复杂度为O(1)

空间复杂度

使用了一个变数total，和一个变数i，函式不会因为x变大了，需要多宣告变数，所以空间复杂度为O(1)

• 范例3

 def example_3(x):
  total = 0
  for i in range(x):
    for j in range(i, x):
      total += i * j
  return total
example_3(10)

时间复杂度

双重回圈

i = 0的时候，j会执行x次加法和x次乘法

i = 1的时候，j会执行x-1次加法和x-1次乘法

...

总共会执行几次加法跟乘法? (x+x-1+...+1)次加法和乘法

套用梯形公式: 上底加下底乘与高除以2

(x+1)x/2 = (x^2 +x) /2

取最高项扣掉系数

就会得到结果: O(N^2)

空间复杂度

使用了一个变数total，一个变数i和一个变数j，函式不会因为x变大了，需要多宣告变数，所以空间复杂度为O(1)

Reference

由于这篇是参考我所学习的课程加上网路资源，再经过自己的消化而来，如果有地方原作者觉得不妥，都请马上与我联系喔，我会马上移除，感谢

https://hiskio.com/packages/1vyM4lw7p

https://ithelp.ithome.com.tw/articles/10216436

https://zh.wikipedia.org/wiki/时间复杂度