当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

算法的时间复杂度

发表于: 2013-08-07   作者:追梦--   来源:转载   浏览:
摘要: 算法的时间复杂度     分析一个算法的好坏,时间复杂度是一个非常重要的标准。我们一般用O()表示一个算法的复杂度。   常见的算法时间复杂度有(由小到大):    O(1)常数阶   O(logn)对数阶   O(n)线性阶   O(nlogn)   O(n^2) &n
算法的时间复杂度
    分析一个算法的好坏,时间复杂度是一个非常重要的标准。我们一般用O()表示一个算法的复杂度。
  常见的算法时间复杂度有(由小到大):
  
O(1)常数阶   O(logn)对数阶   O(n)线性阶   O(nlogn)   O(n^2)   O(n^3) 
| --------             p问题(时间复杂度为上)               -----------|

O(2^n)    O(n!)
|-NP问题(复杂度为上)-|

    计算时间复杂度可分为递归和非递归两种:

  举一个简单的例子:计算斐波拉契数列  f (n) = f (n-1) +f (n-2)   (n  <  45)
    有些人第一眼看到这个问题,觉得用递归十分方便,便毫不犹豫的用了递归(这是某大学的一个考研题,很多人采用了这种算法,但是当他们将程序提交上去,在规定时间内都未能给出答案,他们都觉得不知所云),其实当我们计算过时间复杂度后,出现这个问题的原因就一目了然了。

    如果我们采用递归的方式,那么我们设进入一次递归(一个基本操作)程序运行的时间为一个单位时间
故计算       T (n) = T (n-1) + T (n-2)  + 1
       变形  T (n) + 1 = T (n-1)  + 1 + T (n-2)  + 1
       令    B (n) = T (n)+1
       所以  B (n) = B (n-1) + B (n-2)
       可见 B (n) 也是一个斐波拉契数列
       所以时间复杂度 T (n) = B (n) -1 = f (n)
    当n = 45 时,斐波拉契数列的值在 2,100,000,000 ,这意味着当我们计算斐波拉契的第45项时,我们要执行21亿次基本操作,这是不可想象的!!!因为在递归的过程中执行了大量的无用的重复计算!!!

    如果我们采用非递归的方法递推的话,十分简单,时间复杂度为 O (n)

    我在这里并不是说递归的时间复杂度一定比非递归的时间复杂度高,而是说明对于同一个问题,有不同的算法去解决这个问题,我们在之前一定要分析算法的时间复杂度。否则我们写的程序对时间的开销是不可估量的。而我们在写递归的时候,要特别注意里面嵌套了多个递归的情况。

算法的时间复杂度

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1.空间复杂度 算法中包含原操作次数的多少叫做算法的时间复杂度,用它来衡量一个算法的运行时间性能
1.空间复杂度 算法中包含原操作次数的多少叫做算法的时间复杂度,用它来衡量一个算法的运行时间性能
在信息化的时代里每个人都应该懂一点编程。重复性的机械劳动,都应该交给机器去做,从而把人的精力
求解算法的时间复杂度的具体步骤: ⑴ 找出算法中的基本语句; 算法中执行次数最多的那条语句就是基
算法的时间复杂度和空间复杂度-总结 分类: 数据结构与算法 2013-09-20 16:01 1991人阅读 评论(0)
常用的排序算法的时间复杂度和空间复杂度 原文:http://www.cnitblog.com/houcy/archive/2009/07/24
今天学习了数据结构中的算法,了解了算法中有2个概念【时间复杂度】、【空间复杂度】 顾名思义,意
算法的时间复杂度和空间复杂度-总结 通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上
算法的时间复杂度和空间复杂度-总结 通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上
[大整数乘法]分治算法的时间复杂度研究 开篇 最近研究分治算法,对大整数算法(包括加减乘数)、str
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号