关于算法时间复杂度杂谈

算法时间复杂度分析很重要,我们要优化代码,让计算机轻松一点。

算法分析,在n个随即数中查找某个数字,最好的情况是第一个数字就是,此时时间复杂度为O(1),若最后一个数字才是我们要找的,那么时间复杂度 是O(n),这是最坏的情况。而平均运行时间是从概率的角度看,若数字在每一个位置都可能出现,则平均查找次数为n/2次。

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。可现实中,平均运行时间很难通过分析得到,一般都是通过运行一定数量的实验数据后估算而来的。而最坏运行时间是一种保证,那就是运行时间不会再坏了。在应用中,这是最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况下的运行时间。即,时间复杂度是最坏情况下的时间复杂度。

原文地址:https://www.cnblogs.com/nannanITeye/p/3431094.html