百度百科描述
时间复杂度: http://baike.baidu.com/view/104946.htm?fr=aladdin
空间复杂度: http://baike.baidu.com/view/540497.htm?fr=aladdin
算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。(算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度)。
一、定义
时间复杂度
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。
空间复杂度:
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
二、 时间复杂度 计算方法
1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),
因此,算法的时间复杂度记做:T(n)=O(f(n))
分析:随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。
2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,
再找出 T(n) 的同数量级(它的同数量级有以下:1,log(2)n,n,n log(2)n ,n的平方,n的三次方,
2的n次方,n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,
则时间复杂度T(n) = O(f(n))
三、比较
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,
可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间
复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有
性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑
算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的
机器系统环境等各方面因素,才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为
算法的复杂度。
相关推荐
对时间复杂度和空间复杂度进行超级详细的讲解
对java的8种排序方法的空间复杂度和时间复杂度,进行了一个简单的统计
算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
数据结构与算法笔记:时间复杂度和空间复杂度
时间复杂度和空间复杂度,大O表示法【数据结构和算法入门2】
时间复杂度和空间复杂度.url
算法复杂度——时间复杂度和空间复杂度.doc
信息学奥赛算法时间复杂度和空间复杂度计算 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。 时间效率被称为时间复杂度 空间效率被称作空间复杂度
算法的时间复杂度和空间复杂度-总结.doc
学习电脑信息常用的排序算法的时间复杂度和空间复杂度
Python实现二分查找和哈希查找的示例代码及其时间复杂度和空间复杂度的分析
算法设计目标与时间复杂度与空间复杂度.ppt
相关知识介绍(所有定义只为帮助读者理解相关概念,并非严格定义)
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
这是一个关于编程的资源,旨在帮助学习者深入了解和掌握相关概念和技能。资源提供了多样化的内容,包括详细的教程、示例代码、实践项目和练习题。它适用于各种级别的学习者,无论是初学者、中级学习者还是高级学习者...
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
时间复杂度的理解前言定义(1)时间频度(2)时间复杂度(3)最坏时间复杂度和平均时间复杂度最坏时间复杂度和平均时间复杂度(1)最坏时间复杂度(2)平均时间复杂度尾:求时间复杂度综上: 前言 算法复杂度分为...