【数据结构】时间复杂度（加法乘法规则、渐近时间复杂度、循环时间复杂度总结

2.2 时间复杂度

• 什么���时间复杂度？

  评估算法时间开销

  T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))

  在实际求解中，只留表达式中最高阶的部分，丢弃其他部分。

• 如何求解？

  • 求解步骤

    1.找到一个最深层的基本操作；

    2.分析该操作执行次数x与问题规模n的关系** x = f ( n ) x=f(n) x=f(n)**；

    3.x的数量级 O ( x ) O(x) O(x)就是时间复杂度 T ( n ) T(n) T(n)；

  • 求解原则

    1.顺序执行的代码只会影响常数项，可忽略。

    2.只需挑一个基本操作分析它的执行次数与n的关系即可。

    3.如果有多层嵌套循环，只需关注最深层循环了几次。

  • 规则

    • 1.加法规则

      T ( n ) = T 1 ( n ) + T 2 ( n ) = O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) T(n)=T1​(n)+T2​(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

    • 2.乘法规则

      T ( n ) = T 1 ( n ) ∗ T 2 ( n ) = O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) T(n)=T_1(n)*T_2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)) T(n)=T1​(n)∗T2​(n)=O(f(n))∗O(g(n))=O(f(n)∗g(n))

    • 常见渐近时间复杂度

      O ( 1 )