数据结构 之 算法时间复杂度

来源:http://www.sh-fengwen.com 作者:家常菜谱 人气:65 发布时间:2019-09-11
摘要:上一篇《数据结构和算法》中我介绍了数据结构的基本概念,也介绍了数据结构一般可以分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构和图形结构。物理结构

上一篇《数据结构和算法》中我介绍了数据结构的基本概念,也介绍了数据结构一般可以分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储结构和链式存储结构。并且也介绍了这些结构的特点。然后,又介绍了算法的概念和算法的5个基本特性,分别是输入、输出、有穷性、确定性和可行性。最后说阐述了一个好的算法需要遵守正确性、可读性、健壮性、时间效率高和存储量低。其实,实现效率和存储量就是时间复杂度和空间复杂度。本篇我们就围绕这两个"复杂度"展开说明。在真正的开发中,时间复杂度尤为重要,空间复杂度我们不做太多说明。

<big>版权声明:本文为 Codeagles 原创文章,可以随意转载,但必须在明确位置注明出处!!!</big>

时间复杂度和空间复杂度是算法效率的度量方法。也就是说,一个好的算法取决于它的时间复杂度和空间复杂度。函数的渐近增长:给定两个函数f,如果存在一个整数N,使得对于所有的n>N,f大。那么,我们说f的增长渐近快于g。

想要学会算法时间复杂度,那么就要先弄清楚几个概念。

翻译过来就是:如果存在一个临界值,使得f>g永远成立,那么我们就认为"f的增长渐近快于g"。这里我拿3个函数的增长曲线来说明问题。如下图:函数一:X = 3n 注释:3乘以n函数二:Y = 2n^2 注释:n的平方乘以2函数三:Z = 2n^2 + 3n 注释:n的平方乘以2 + 3乘以n

  1. 什么是算法时间复杂度?
  2. 它有什么用呢?
  3. 写法记作 T(n)=O(f(n))

图片 1

  • T(n):语句执行的总次数关于n的函数
  • n:问题规模
  • f(n):问题规模n的某个函数
  • 用O()来体现算法时间复杂度的记法

当n=1时,Y < X < Z.当n=2时,X < Y < Z.所以,存在一个值,这个值位于1和2之间,使得X < Y < Z永远成立。我们就称Y的渐进增长快于X,Z的渐进增长快于Y,当然,根据传递性规则,Z的渐进增长也快于X。

时间复杂度的定义是:如果一个问题的规模是n,解决这一问题所需算法所需要的时间是n的一个函数T(n),则T(n)称为这一算法的时间复杂度。
所谓算法时间复杂度就是一句话:算法中基本操作的执行次数。既然是T(n)的函数,随着模块n的增大,算法执行的时间的增长率和T(n)的增长率成正比,所以T(n)越小,算法的时间复杂度越低,算法的效率越高。

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

那么它有什么用呢?刚才也说了,可以通过f(n)的函数关系来评估算法的效率问题,说白了就是通过时间复杂度来看算法的好坏

1.用常数1取代运行时间中的所有加法常数。2.在修改后的运行次数函数中,只保留最高阶项。3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。最后,得到的最后结果就是时间复杂度。

值得注意的是:有的算法中基本操作执行次数不仅仅跟初始输入的数据规模(n)有关,还和数据本身有关。例如一些排序算法,同样n个待处理数据,数据初始有序性不同,基本操作执行次数也会不同。如果算法中有特殊要求,一般依照使得基本操作执行次数最多的输入来计算时间复杂度,即将最坏的情况最为算法时间复杂度的度量。

本文由美高梅游戏平台网站发布于家常菜谱,转载请注明出处:数据结构 之 算法时间复杂度

关键词:

上一篇:没有了

下一篇:没有了

最火资讯