数据结构之时间复杂度分析

2019-09-22
小编: 宝宝
正體

分享到：

导读: 正文:开篇我们先思考这么一个问题：一台老式的 CPU 的计算机运行 O(n) 的程序，和一台速度提高的新式 CPU 的计算机运 O(n2) 的程序。谁的程运行效率高呢？答案是前者优于后者。为什么

丝瓜网小编提示，记得把"数据结构之时间复杂度分析"分享给大家！

正文:

开篇我们先思考这么一个问题：一台老式的 CPU 的计算机运行 O(n) 的程序，和一台速度提高的新式 CPU 的计算机运 O(n2) 的程序。谁的程运行效率高呢？

答案是前者优于后者。为什么呢？我们从时间复杂度分析就可以知道。

1、什么是时间复杂度？

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

这样用大写 [ O( )] 来体现算法时间复杂度的记法，我们就称之为大O记法。例如：O(n)、O(1)、O(n2)、O(log n) 等等。一般情况下，随着 n 的增大，T(n) 增长最慢的算法为最优算法。

2、推导大O阶的方法

如何推导大O阶的表示方法，总结了三句口诀：

用时间1取代运算时间中的所有加法常数。

在修改后的运行的函数中，只保留最高阶项。

如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

说了太多文字显得太抽象，我们来看看一个例子你就明白了。

如图这个时间复杂度你知道是多少吗？

丝瓜网 crfgs.com

点击展开剩余内容