0

0

算法复杂度主要包括什么

hzc

hzc

发布时间:2020-06-24 11:44:59

|

18544人浏览过

|

来源于php中文网

原创

算法复杂度主要包括什么

算法复杂度:

时间复杂度

    在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

    为了计算时间复杂度,我们通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。

    相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为T(n),定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。时间复杂度可以用函数T(n) 的自然特性加以分类,举例来说,有着T(n) =O(n) 的算法被称作“线性时间算法”;而T(n) =O(M^n) 和M= O(T(n)) ,其中M≥n> 1 的算法被称作“指数时间算法”。

    一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
  一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
  在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。

时间频度

    一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

空间复杂度

    与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:

    S(n)=O(f(n))

Android的资源与国际化设置 中文WORD版
Android的资源与国际化设置 中文WORD版

本文档主要讲述的是Android的资源与国际化设置;资源是外部文件(不含代码的文件),它被代码使用并在编译时编入应用程序。Android支持不同类型的资源文件,包括XML,PNG以及JPEG文件XML文件根据描述的不同有不同格式。这份文档描述可以支持什么样的文件,语法,以及各种格式。希望本文档会给有需要的朋友带来帮助;感兴趣的朋友可以过来看看

下载

    算法执行期间所需要的存储空间包括3个部分:

  • 算法程序所占的空间;

  • 输入的初始数据所占的存储空间;

  • 算法执行过程中所需要的额外空间。

    在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术。

相关专题

更多
vlookup函数使用大全
vlookup函数使用大全

本专题整合了vlookup函数相关 教程,阅读专题下面的文章了解更多详细内容。

26

2025.12.30

金山文档相关教程
金山文档相关教程

本专题整合了金山文档相关教程,阅读专题下面的文章了解更多详细操作。

28

2025.12.30

PS反选快捷键
PS反选快捷键

本专题整合了ps反选快捷键介绍,阅读下面的文章找到答案。

25

2025.12.30

表格中一行两行的方法
表格中一行两行的方法

本专题整合了表格中一行两行的相关教程,阅读专题下面的文章了解更多详细内容。

3

2025.12.30

cpu温度过高解决方法大全
cpu温度过高解决方法大全

本专题整合了cpu温度过高相关教程,阅读专题下面的文章了解更多详细内容。

5

2025.12.30

ASCII码介绍
ASCII码介绍

本专题整合了ASCII码相关内容,阅读专题下面的文章了解更多详细内容。

31

2025.12.30

GPS是什么
GPS是什么

本专题整合了GPS相关内容,阅读专题下面的文章了解更多详细内容。

3

2025.12.30

wifi拒绝接入
wifi拒绝接入

本专题整合了wifi拒绝接入相关教程,阅读下面的文章了解更多详细方法。

9

2025.12.30

丰网速运介绍
丰网速运介绍

本专题整合了丰网速运查询入口以及相关内容,阅读专题下面的文章了解更多内容。

3

2025.12.30

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Vue.js 微实战--十天技能课堂
Vue.js 微实战--十天技能课堂

共18课时 | 1.1万人学习

PHP基础入门课程
PHP基础入门课程

共33课时 | 1.9万人学习

前端HTML5+CSS3(女神版)
前端HTML5+CSS3(女神版)

共199课时 | 26.7万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号