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

数据结构与算法——算法速率

发表于: 2012-11-08   作者:ciaos   来源:转载   浏览:
摘要:   O()表示法是处理近似计算的一种数学途径,当我们写下某个特定的排序算法对n个记录进行排序所需时间是O(n2)时,我们的意思是,最坏情况下,所需时间随着n的平方变化。O()表示法对我们在度量时间,内存等的值设置了上限。   有时我们会遇到复杂的O()函数,随着n的增大, 最高阶的项会主宰函数的值,习惯做法是去掉所有低阶项,对任何常数项不予考虑。如O(n2+3n)和O(n

 

O()表示法是处理近似计算的一种数学途径,当我们写下某个特定的排序算法对n个记录进行排序所需时间是O(n2)时,我们的意思是,最坏情况下,所需时间随着n的平方变化。O()表示法对我们在度量时间,内存等的值设置了上限。

 

有时我们会遇到复杂的O()函数,随着n的增大, 最高阶的项会主宰函数的值,习惯做法是去掉所有低阶项,对任何常数项不予考虑。如O(n2+3n)和O(n2)一样等价,这实际上是O()表示法的弱点。某个O(n2)算法可能比O(n2)算法快1000倍,但是从表示法中看不出来。

 

下面是一些常见的各种算法运行时间

 

附表一:

 

O(1) 常量访问(访问数组元素,简单语句)
O(lg(n)) 对数型(二分查找)lg(n)是 log2n缩写
O(n) 线性型(顺序查找)
O(nlg(n)) 比线性差,但不会差很多(快排,堆排序平均运行时间)
O(n2) 平方律型(冒泡,选择,插入排序)
O(n3) 立方型(2n ×  n矩阵相乘)
O(Cn) 指数型(旅行家问题,集合划分)

 

附表二:

 

排序法

最差时间分析 平均时间复杂度 稳定度 空间复杂度
冒泡排序 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)
希尔排序 O O 不稳定 O(1)

数据结构与算法——算法速率

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号