• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

为什么这个算法执行时间这么长?

为什么这个算法执行时间这么长?

浏览次数:
评论次数:
编辑: 阳煦
信息来源: 51CTO博客
更新日期: 2021-06-11 01:09:10
摘要

为什么这个算法要执行这么长时间?,今天应做的事没有做,明天再早也是耽误了。——裴斯泰洛齐你好,我是悦创。最近真的有好久的时间没有与读者们想见,因为时间关系和不知道写什么可以吸引到你们。想了好久,最终写了此篇文章。感谢你们陪伴我走过了这段时间。就想写个基础,也是很多人不去写的文章。如果,你有阅读我的文章会发现,我的文章都是非常的长的。

  • 资讯详情

今天该做的事不做,明天就耽误了。—— Pestalozzi

你好,我是月闯。

最近真的很久没见读者了,因为时间关系和不知道写什么能吸引你。想了很久,终于写出了这篇文章。谢谢你陪我度过这段时间。就是想写个基础,也是很多人不写的文章。

如果你看过我的文章,你会发现我的文章很长。我花了很多心血,希望这些文章对你有帮助。

什么是时间复杂度

用高级语言编写的程序的运行时间主要取决于三个因素:

算法的方法和策略;

问题的输入规模;

计算机执行指令的速度。

分析

问题的投入规模是客观的、有限的。为了加快算法的效率,一定不能影响问题的输入规模。

虽然计算机执行指令的速度可以显著提高,但其开发时间长且不确定,不可能整天期待计算机性能的提高。

因此,提高算法的效率,减少程序的运行时间,改进算法的策略是非常重要的。

在解释时间复杂度之前,我们需要引入一个概念,时间频率。

时间频率表示算法中执行的语句数,也可以称为语句频率。

显然,时间频率越高,算法运行的时间越长。时间频率也可以写成T(n),其中n是问题的规模,即输入值的规模。

时间复杂度的具体定义是:如果有一个辅助函数f(n),则f(n)T(n){ f(n)} \ over { T(n)} T(n)f(n)(当n趋近于无穷大时)的极限值为不等于零的常数,则称之为f(n)f(n T(n)=O f(n)T(n)=Of(n)T(n)=Of(n)。

O (f (n)) O(f(n)) O(f(n))称为算法的渐进时间复杂度。数学上用大O O O符号来描述函数的渐近上界。

以上是纯数学分析,不太懂的读者可以理解时间复杂度是算法运行时间和输入规模的关系。

时间复杂度是渐进的

如果我们把算法中的一次计算取为1 ^ 1 ^ 1,那么如果有n n n个输入值,算法会对每个输入值做一次运算,那么整个算法的计算量就是n ^ n ^ n,这时我们可以说这个算法是O (n) O(n) O(n)。

同理,如果仍然有n ^ n ^ n个输入值,但算法需要对每个输入值重复运算n ^ n次,那么整个算法的计算复杂度为n ^ n=n ^ 2n * n=n ^ 2nn=n ^ 2,时间复杂度为o(n ^ 2)o(n ^ 2)o(n ^ 2)n ^ 2)。这时如果对每个输入值做一个运算,这个运算需要重复N ^ 1 ^ N ^ 1次,算术运算量变成:$ N *(N ^ 1)=N ^ 2 ^ N $

时间复杂度变成o (n2n) o (n2n) o (n2n)了吗?如上所述,时间复杂度检查当输入量趋向于无穷大时的情况,因此当n ^ n ^ n趋向于无穷大时,n2n 2n2支配算法的运行时间,而n ^ n ^ n在$ n^2 $之前是不重要的,这不包括在时间复杂度中。

换句话说,因为n2n2n2n渐近(取极限时)等于n2n2n2。另外,就运行时间而言,n n n之前的常数因子远不如输入规模$ n $,所以可以忽略,也就是说,$ o(n ^ 2 $)和o(n ^ 2)o(\ frac { n ^ 2 } { 2 })o(2 N2)的时间复杂度相同,都是o。

时间复杂度分析

让我们先来看一段代码:

def平方(n):

Partial_Sum=0

对于范围(1,n 1):中的I

Partial_Sum=i * i

返回部分和

代码的第二行只需要一个操作,在第三行的for循环中,I从1加到n。过程包括I初始化,I累加,I范围判断,分别消耗一次运算,N次运算,n 1次运算。

到目前为止,前三行代码已经被操作了2 n 3 2n 3 2n 3次。第四行是乘加赋值组合的代码。乘法需要N次运算,加法需要N次运算,赋值需要N次运算。所以四线已经运行了3 x n 3xn 3xn次。最后一行返回消耗一次的操作。

一般来说,这个代码需要操作2 n 3 3 n 1=5 n 4 2n 3 3n 1=5n 4 2n 3 3n 1=5n 4次。根据上面的渐进原理,这个代码的时间复杂度是O (n) O(n) O(n)。

通过以上

分析,可以看出细致的时间复杂度分析十分繁琐。但毕竟时间复杂度追求渐进原则,所以在这里为大家整理了一下快速算时间复杂度的技巧:

循环结构
for i in range(1, k*n+m+1):
	i += 1

上示代码中的 n 为输入规模,k,m 均为已知常数。因此根据渐进原则,只要 for 循环的循环范围是在 n 的有限倍数以内(range 的上界始终可以被表示为 $ k*m+n $ 的形式),则一个 for 循环的时间复杂度必然为 O ( n ) O(n) O(n)。

for i in range(n):
	for j in range(n):
    	Partial_Sum += 1

我们将两个 for 循环迭代在一起。有 n 个不同的 i,每个i 会对应 n 的不同的 j 的情况下,会有 n ∗ n = n 2 n*n = n^2 n∗n=n2 次第三行的操作。在这里我们可以说这段代码的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。实际上,真实的运算次数会有 k ∗ n 2 k*n^2 k∗n2 次(k为一个常数),其中 k 始终是有限的尽管 k 有时会非常大。

综上所述,我们可以总结出循环结构时间复杂度的一些规律:

  • 无论是 for 还是 while 循环,只要循环的范围可以表示为 k ∗ n + m k * n + m k∗n+m ,则该循环的时间复杂度为 O ( n ) O(n) O(n);
  • 如果循环中嵌套循环,则时间复杂度将便成每一层循环的时间复杂度相乘的结果;
  • 在决定时间复杂度时,往往只需要关注层数最多 for 循环结构的时间复杂度,因为其它循环的时间复杂度很大可能上会被忽略。
递归结构
def feb(n)
    if n <= 1:
        return 1
    else:
        return feb(n - 1) + feb(n - 2)

如上所示的是一个计算斐波那契数列函数。而我们都是道斐波那契数列的公式为:

f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)

假设当输入规模为时该函数的运行次数为 T ( n ) T(n) T(n) ,通过上示公式我们可以得到:

T ( n ) = ( T ( n − 1 ) + 1 ) + ( T ( n − 2 ) + 1 ) T(n) = (T(n-1)+1)+ (T(n-2)+1) T(n)=(T(n−1)+1)+(T(n−2)+1)

由于常数不会影响到函数整体的时间复杂度,所以可以被简化为:

T ( n ) = T ( n − 1 ) + T ( n − 2 ) T(n) = T(n-1)+T(n-2) T(n)=T(n−1)+T(n−2)

到这一步,我们已经知道当输入规模为n时,斐波那契数列函数时间复杂度的递推公式,而我们只需求出通项公式即可分析出其时间复杂度为 O ( ( 1 + 5 2 ) n ) O((\frac{1+\sqrt5}{2})^n) O((21+5 ​​)n),约为 O ( 1.61 8 n ) O(1.618^n) O(1.618n),简化默认为指数级复杂度 O ( 2 n ) O(2^n) O(2n) 。可以看出,该斐波那契数列函数的时间复杂度成指数增长,说明这是较为低效的一个递归函数。

小结

在了解算法本质的同时,要掌握时间复杂度来判断一个算法的效率和实用性。相同问题时,算法的复杂度越低,证明算法的效率越高。本质上,输入规模往往是对空间复杂度与时间复杂度影响最大的因素。对于时间复杂度来说,输入量越多,所需处理的数据量越多,计算次数越多,算法运行的时间越多。

08-操作符和数据类型总结
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多