【数据结构】时间复杂度（加法乘法规则、渐近时间复杂度、循环时间复杂度总结
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 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
-
时间复杂度分类
最坏时间复杂度、平均时间复杂度、最好时间复杂度
只考虑最坏时间复杂度。
-
循环时间复杂度总结
原文地址：https://blog.csdn.net/m0_61628700/article/details/136284852
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！