算法的时间复杂度度可以用程序运行的时间来衡量吗

来源：蜘蛛抓取(WebSpider) 时间：2019-01-04 00:42 标签： 算法的时间复杂度

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

　　算法的算法的时间复杂度度是刚开始接触算法和数据结构时的概念，在真正使用的时候有时候常常忘记它的推导公式最近准备校招，把二叉树、排序、查找等这些经典的算法复习了一遍这次把这些都整理成博客以便以后查看，复习计划接近尾声这两天老是不在状态，学习图的时候有点晕乎乎今天反过头来把算法的时间复杂度度的求解法整理一下，还是颇有收获以前很多地方自己存在着理解误差。希望对大家也有所帮助囿不对的地方还请多指教。

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

一般用大写O()来表示算法的算法的时间复杂喥度写法，通常叫做大O记法

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

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的運行函数中只保留最高阶项
  3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数

这个算法的运行次数f(n) = 3,根据推导大O阶的方法第一步是將3改为1，在保留最高阶项是它没有最高阶项，因此这个算法的算法的时间复杂度度为O(1);

上面的两段代码中其实无论n有多少个，本质是是3佽和12次的执行差异这种与问题的大小无关，执行时间恒定的算法成为具有O(1)的算法的时间复杂度度，又叫做常数阶

注意：不管这个常數是多少，3或12都不能写成O(3)、O(12)，而都要写成O(1)

此外对于分支结构而言，无论真假执行的次数都是恒定不变的不会随着n的变大而发生变化，所以单纯的分支结构（不在循环结构中）其算法的时间复杂度度也是O(1)。

线性阶的循环结构会复杂一些要确定某个算法的阶次，需要確定特定语句或某个语句集运行的次数因此要分析算法的复杂度，关键是要分析循环结构的运行情况

/*算法的时间复杂度度为O(1)的程序*/
/*算法的时间复杂度度为O(1)的程序*/

因为每次count*2后，距离结束循环更近了也就是说有多少个2 相乘后大于n，退出循环

因此这个循环的算法的时间复雜度度为O(logn)

/*算法的时间复杂度度为O(1)的程序*/

上面的程序中，对于对于内层循环它的算法的时间复杂度度为O(n)，但是它是包含在外层循环中再循环n次，因此这段代码的算法的时间复杂度度为O(n2)

/*算法的时间复杂度度为O(1)的程序*/

但是，如果内层循环改成了m次算法的时间复杂度度就为O(n*m)

/*算法的时间复杂度度为O(1)的程序*/

注意：上面的内层循环j = i ;而不是0

因为i = 0时，内层循环执行了n次当i=1时，执行了n-1次……当i=n-1时执行了1次，所以总的執行次数为：

根据大O推导方法保留最高阶项，n2/2 然后去掉这个项相乘的常数，1/2

因此这段代码的算法的时间复杂度度为O(n2)

下面，分析调用函数时的算法的时间复杂度度计算方法：

函数的算法的时间复杂度度是O(1)因此整体的算法的时间复杂度度为O(n)。

/*算法的时间复杂度度为O(1)的程序*/

和第一个的不同之处在于把嵌套内循环放到了函数中因此最终的算法的时间复杂度度为O(n2)

再来看一个比价复杂的语句:

/*算法的时间复杂度喥为O(1)的程序*/

根据推导大O阶的方法，最终它的算法的时间复杂度度为：O(n2)

算法的时间复杂度度所耗费的时间是：

我要回帖

更多关于 算法的时间复杂度 的文章

 

随机推荐