⑴ 算法的时间复杂度是指什么
算法的时间复杂度是指该算法举虚枯所需要的计算工作量随问题规模增加而增加的趋势,也就是算法的运行时间与问题规模之间的关系。
1、算法时间复杂度的概念
算法时间复杂度是指在分析算法性能时,关注的是该算法的计算复杂程度。主要是根据算法中基本操作的执行次数来估算算法的效率。算法的时间复杂度在一定程度上衡量了算法的好坏,是在进行算法性能分析时的一项基本指标。
2、计算时间复杂度的方法
通过代码分析可以得出一个算法的时间复杂度,一般采用大O表示法。大O表示法是一种用于描述算法复杂度的表示方法。
用一个大O符号加上一个括号括起来的函数描述算法复杂度,在大O符号后面的函数里,n表示数据输入的总量,T(n)表示算法执行所需的时间复杂度函数。
5、总结:
算法的时间复杂度是分析算法效率的一种常用指标,可以通过大O记号表示算法需要执行的操作次数,常见类型包括常数时间复杂度、线性时间复杂度、对数时间复杂度、平方时间复杂度和指数时间复杂度。
在实际应用中,需要根据具体需求综合考虑时间复杂度和空间复杂度。
⑵ 大O表示法
表示时间的大O符号,是用来描述算法效率的语言和度量单位。
大O表示法分析了算法的运行时间如何随列表的增长而增长,指出了算法最糟情况下的运行时间。
n为列表的长度,(n)作为大O表示法的操作数。
大O表示法通常不考虑常量,因为如果这两种算法的大O运行时间不同,这个常量将无关要紧。
大O表示法不考虑乘以、除以、加上或减去的数字。如O(n+26)、O(n-26)、O(n*26)、O(n/26),它们都应该表示为O(n)。
如下图:
其中Ο(log2n )、Ο(n)、 Ο(nlog2n )、Ο(n2)和Ο(n3)称为多项式时间,而Ο( 2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者(即多项式时间复杂度的算法)是有效算法,把这类问题称为P(Polynomial,多项式)类问题,而把后者(即指数时间复杂度的算法)称为NP(Non-Deterministic Polynomial,非确定多项式)问题。
1、《算法图解》 https://www.manning.com/books/grokking-algorithms
2、《算法的基本概念》 https://www.zybuluo.com/defias/note/286416