数据结构与算法学习笔记(5):图解数据结构与算法-复杂度分析（四）：浅谈最好、最差及平均情况时间复杂度分析...

立即学习:https://edu.****.net/course/play/29510/421555?utm_source=blogtoedu

复杂度分析（四）：浅谈最好、最差及平均情况时间复杂度分析

最好情况时间复杂度(Best Case Time Complexity)

最坏情况时间复杂度(Worst Case Time Complexity)

平均情况时间复杂度(Average Case Time Complexity)

【例】

其中for循环遍历了整个数组，时间复杂度唯一的

 

如何优化？

此时，找到数据后就会结束，时间复杂度是一个动态的区间

 

这种情况还可以怎样衡量？

这样计算有怎样的问题？

问题是——没有计算每次查找时可能找到的概率

这个值就是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

 

小结

在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况，使用一个复杂度就可以满足需求了。

只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分