概述

主要总结面试蛋糕中用来表达算法复杂读的O的相关知识和心得。
网页地址：https://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity?section=algorithmic-thinking&course=fc1

基础知识

• 目的
  The Big O notation is the language we use for talking about how long an algorithm takes to run.
  O表达式是一种我们用描述一个算法运行中耗时多少的语言表达方式。
• 详细描述
  with big o notation we express the runtime in terms of - brace youself - how quickly it grows relative to the input.
  我们使用O表达式，相对输入的增长速度来描述运行时。
  从如下几个方面阐述：
  1. how quickly the runtime grows(运行时的增长速度)
     我们很难证实一个算法的真正的运行时间，这个跟处理器的处理效率相关，和计算机如何运行相关，等等，相对于直接使用运行时间，O表达式是描述运行时的增长速度。
  2. relative to the input(相对于输入)
     如果我们直接计算运行时间，那么我们可以使用秒来描述速度；当我们计算运行时的增长速度，我们需要基于其他的东西来描述我们的速度，对于O表达式，我们使用输入的大小，通常称为n。
  3. as the input gets arbitrarily large(输入变得任意大)
     当n比较小的时候，我们的算法中一些步骤显的比较重要（耗时占比大），但当n很大时，这些步骤就不值得一提了。我们最关心的时随着输入增大而增长最快的东西，当n非常大的时候，其他东西就很不值得一提了。（渐进线）

其他注意点

• n could be the actual input, or the size of input(n可能是输入的值，也可能是输入的大小)
• Drop the constants(删除常量)
• Drop the less significant terms(删除一些不重要的条款)
• We usually talking about the "worse case"(我们经常讨论最坏情况)
  有时最坏情况比最好情况要坏的多，面试的时候，也可以通过明确的表述最坏情况，来打动面试官。

Space complexity(空间复杂性)：the final frontier(最后的边界)

有时候，对于花费更短时间，我们更希望使用更少的存储空间。讨论空间复杂和上面讨论时间复杂很相似，都是相对于输入而言。
当我们讨论空间复杂性时，一般讨论的是额外增加的空间；对于输入占用不考虑。
时间复杂性和空间复杂性，在设计算法时，应进行权衡利弊。

Big O analysis is awesome expect it is not(Big O分析很棒，除了它不是)

使用Big O分析时，也要注意如下几点，并不是严格的按照上面的注意点而行，需进行甄别。

1. Big O强调忽略常量，但常量有时也很重要(可以达到很好的优化效果)；
2. 注意避免过早优化
   有时优化时间或空间对可读性或编码时间有负面影响，对于一些初创或代码开发初期，编写易于快速发布和易读的代码更为重要，尽管运行时间不及预期。

共勉

一个伟大的工程师，知道如何在运行时，空间，实现时间，可维护性和可读性之间取得适当平衡。
您应该发展技能以查看时间和空间优化，以及判断这些优化是否值得的智慧。