时间复杂度

大 O 复杂度表示法

1. 假设每行代码执行的时间都是一样的。为 unit_time
2. 所有代码的执行时间T(n)与每行代码的执行次数n成正比
3. 大O公式 T(n) = O(fn)
4. 公式讲解: T(n) 我们已经讲话了，它表示代码执行的时间。n表示数据规模的大小。f(n)表示每行代码执行的次数总和。公式中的O表示代码的执行时间T(n)与f(n)表达式成正比。
5. 大O时间复杂度表示法，大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。所以也叫渐进时间负责度。 简称时间复杂度。
6. 当n很大时，你可以把它想象成 10000、100000。而公式中的低阶系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n2)。

时间复杂度分析

1. 只关注循环执行次数最多的一段代码
   在分析一个算法，一段代码的时间复杂度的时候，也只关注循环次数执行最多的那一段代码就可以了。这段核心代码执行次数的n的量级 就是整段代码要分析的时间复杂度

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

   我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。
   只要是一个已知的数，跟n无关，照样也是常量级的执行时间。
   时间复杂度的概念来说 它表示的是一个算法执行效率与数据规模增长的变化趋势。所以不管常量的执行时间多大，我们都可以忽略掉。因为他本身对增长趋势没有影响。总的时间复杂度就等于量级最大的那段代码的时间复杂度

3. 乘法法则:嵌套代码的复杂度等于前套内外代码复杂度的乘积。

   我们可以把乘法法则看成是嵌套循环

• 为了表示在不同情况下的不同时间复杂度。引入三个概念：
  • 最好情况时间复杂度
  • 最坏情况时间复杂度
  • 平均情况时间复杂度
• 平均情况时间复杂度
  • 也加做加权平均时间复杂度或者期望时间复杂度
• 均摊时间复杂度 -- 均还分析(平摊分析)
• 尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度.均摊时间复杂度就是一种特殊的平均时间复杂度。