taoCMS是基于php+sqlite/mysql的国内最小(100Kb左右)的功能完善的CMS管理系统

常见算法时间复杂度

2013-02-17

常见算法时间复杂度:
O(1):
 表示算法的运行时间为常量
O(n): 表示该算法是线性算法
O(㏒2 n): 二分查找算法
O(n2 ): 对数组进行排序的各种简单算法,例如直接插入排序的算法。
O(n3 ): 做两个n阶矩阵的乘法运算
O(2n ): 求具有n个元素集合的所有子集的算法
O(n!): 求具有N个元素的全排列的算法

优<---------------------------<劣

O(1)<O(㏒2 n)< O(n)< O(n2 )< O(2n )

时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2 n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2 )、立方阶O(n3 )、……k次方阶O(nk )、指数阶O(2n )。


若设二叉树的高度为h,除第 h 层外,其它各层 (1h-1) 的结点数都达到最大个数,第 h 层所有的节点都连续集中在最左边,这就是完全二叉树。

 

性质:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
性质四具有n个结点的完全二叉树的深度为「log2n+1

 

查找:

1.       顺序查找

a)         算法简单,适应面广,稳定算法

b)        平均查找长度比较大,当n比较大时,查找效率会很低,时间复杂度为O(n)

2.       折半查找法

a)         针对有序的序列表,不稳定算法

b)        查找速度快,时间复杂度是O(log2n)

3         分块查找

a)         也是针对有序表,不稳定算法

b)        查找速度介于顺序查找和折半查找之间

 

树表查找:

1.    二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

2.    平衡二叉树:棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,查找时间的时间复杂度为O(log2n)

 

排序:

 

排序分类     平均时间       时间复杂度       辅助存储空间

简单排序     O(n2)           O(n2)            O(1)

快速排序     O(nlog2n)       O(nlog2n)         O(nlog2n)

堆排序       O(nlog2n)       O(nlog2n)         O(1)

归并排序     O(nlog2n)       O(nlog2n)         O(n)

 

从平均时间来讲,快速排序是最快的,但是在最坏的情况下,它的时间复杂度(为O(n2))就不如堆排序和归并排序,归并排序所需时间比堆排序省,但是它需要辅助空间,从方法的稳定性来讲,归并排序是一种稳定排序,快速排序和堆排序都是不稳定的。


排序法

最差时间分析平均时间复杂度稳定度空间复杂度
冒泡排序O(n2)O(n2)稳定O(1)
快速排序O(n2)O(n*log2n)不稳定O(log2n)~O(n)
选择排序O(n2)O(n2)稳定O(1)
二叉树排序O(n2)O(n*log2n)不一顶O(n)

插入排序

O(n2)O(n2)稳定O(1)
堆排序O(n*log2n)O(n*log2n)不稳定O(1)
希尔排序OO不稳定O(1)

1、时间复杂度 
(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 
(2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度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)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 2、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。 
(3)渐进时间复杂度评价算法时间性能   主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

2、类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地/"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

类别:技术文章 | 阅读:226928 | 评论:0 | 标签:算法 算法复杂度

想收藏或者和大家分享这篇好文章→

“常见算法时间复杂度 ”共有0条留言

发表评论

姓名:

邮箱:

网址:

验证码:

公告

taoCMS发布taoCMS 3.0.2(最后更新21年03月15日),请大家速速升级,欢迎大家试用和提出您宝贵的意见建议。

捐助与联系

☟请使用新浪微博联系我☟

☟在github上follow我☟

标签云