什么是算法的时间复杂度?

发布时间:2024年01月12日

一、问题

????????算法的时间复杂度是评测算法好坏的主要指标,那么什么是算法的时间复杂度呢?

二、解答

????????算法的时间复杂度度量主要是计算?个算法所?的时间,算法所?的时间主要包括程序编译时间和运?时间。由于?个算法?旦编译成功就可以多次运?,因此忽略编译时间, 在这?只讨论算法的运?时间。

????????算法的运?时间依赖于加减乘除等基本的运算、参加运算的数据的??、计算机硬件 以及操作环境等等。要想准确地计算时间是不可?的。?影响算法时间最为主要的因素是问题的规模,也就是输?量的多少。同等条件下,问题的规模越?,运?的时间也就更?。

????例如,求1+2+3+?+n 的算法,即n个整数的累加求和,这个问题的规模为n。因此,运?算法所需的时
间T是问题规模n的函数,记作 T(n)。

????????为了客观地反映?个算法的执?时间,通常?算法中基本语句的执?次数来度量算法的?作量。?这种度量时间复杂度的?法得出的不是时间量,?是?种增?趋势的度量。 即当问题规模n增?时,T(n)也随之变?。

? ? ? ? 总而言之,当问题规模充分?时,算法中基本语 句的执?次数为在渐进意义下的阶,成为算法的渐进时间复杂度,简称时间复杂度,通常??O记号表示。

?数学语?通常描述为:
    若当且仅当存在正整数c和n0,对于任意n >= n0,都有 T(n)<=c*f(n),则称该算法的渐进时
间复杂度为 T(n) = O((n))(或称算法在O(f(n))中)。

????????对于某些算法即使问题规模相同,如果输?数据不同,则算法运?时间也不同。因此要想全?分析?个算法,需要考虑算法在最好、最坏、平均情况下的时间消耗。

????????由于最好情况出现的概率太?,因此不具代表性,但是,当最好情况出现的概率?时,应该分析最好情况;虽然最坏情况出现的概率也太?,不具代表性,但是分析最坏情况能够让?们知道算法的运?时间最坏到什么程度,这?点在实时系统中很重要;分析平均情况是?较普遍的,特别是同?个算法要处理不同的输?时,通常假定输?的数据是等概率分布的。

????????通过对算法时间复杂度的分析,我们可以总结出这样?条结论:

    在计算任何算法的时间复杂度时,可以忽略所有低次幂和最?次幂的系数,这样可以简化算法
分析,并使注意?集中在增长率上。 下?求?个程序段的时间复杂度,体会?下时间复杂度的计算
?法。

例如,求下?程序段的时间复杂度。

for(i = 1;i < 7;i++) 
sum += i;

//sum += i 是基本语句,执?次数为6,时间复杂度为O(1),此时间复杂度称为常量阶。
注意:

只要T(n)不是问题规模n的函数,?是?个常数,它的时间复杂度均为O(1)

三、总结

????????在科技?度发展的今天,速度是?切事物的标准。?效的算法?先要求具有低的时间复杂度,但是也要综合考虑,不能为追求低的时间复杂度?忽略了其他标准。

文章来源:https://blog.csdn.net/W_Fe5/article/details/135547016
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。