《大话数据结构》数据结构与算法学习笔记3

《大话数据结构》数据结构与算法学习笔记3

算法复杂度

问题的输入规模为n,判断一个算法的效率时,函数中的常数和其他次要项通常可以忽略,而应该更加关注主项(最高阶项)的阶数。——就是和数学分析里判断两个函数高低阶的思路一样。

如果规范一下说法,就是算法时间复杂度——

算法时间复杂度

定义: 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n)). 它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
——用O()里体现算法时间复杂度的记法称为大O记法。

一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。

要分析算法的复杂度,关键就是要分析循环结构的运行情况(特别是看循环语句要执行多少次,且循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数)。

常数阶O(1):执行时间恒定,与问题的输入大小n无关。
线性阶O(n):通常是一个循环体,然后里面的内容是O(1)。
对数阶: 经常出现在条件判断情况下。
**平方阶:**有很多不同的例子,详见书的33-34页。

常见时间复杂度的耗费时间排序:
常数阶<对数阶<线性阶<nlogn阶<平方阶<立方阶<指数阶( 2n) < 阶乘阶 < nn
指数阶及后面的阶数有些不切实际,所以一般不去讨论。

    原文作者:sevures_snape
    原文地址: https://blog.csdn.net/sevures_snape/article/details/114866600
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞