算法之时间复杂度

分析一个算法的运行时间,最重要的就是把核心操作的次数和输入规模关联起来,即找出核心操作与数据输入规模之间的关系,如下图所示。
算法之时间复杂度
比较算法随着输入规模的增长量时,可以有以下规则:
1.算法函数中的常数可以忽略;
2.算法函数中最高次幂的常数因子可以忽略;
3.算法函数中最高次幂越小,算法效率越高。

大O记发:
语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随着n的变化情况并确定T(n)的量级。又因为执行次数=执行时间,所以随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度,其中f(n)是问题规模n的某个函数。记作:T(n)=O(f(n))

基于我们对函数渐近增长的分析,推导大O阶的表示法有以下几个规则可以使用:
1.用常数1取代运行时间中的所有加法常数;
2.在修改后的运行次数中,只保留高阶项;
3.如果最高阶项存在,且常数因子不为1,则去除与这个项相乘的常数。

常见大O时间复杂程度从低到高依次为:
算法之时间复杂度
从平方阶开始,随着输入规模的增大,时间成本会急剧增大,所以,我们的算法,尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度,而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的,那我们可以分为这种算法是不可取的,需要优化

MARK:在时间复杂度可变的情况下,需要考虑最坏情况。