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

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

发表于: 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

    震惊

    震惊

编辑推荐
数据结构与算法 数据结构是计算机学科的重要分支研究领域。数据结构和算法在计算机学科中的地位十分
第一章 数据源和数据项 数据项:数据结构中讨论的最小单位 数据元素使数据项的集合 例如:运动员是
常见排序算法主要有: 插入排序(直接插入排序、希尔排序) 选择排序(直接选择排序、堆排序) 交换
hello,everybody.今天我们来总结一下《大话数据结构》第二章----算法。那么首先,让我们一起回忆一
什么是数据结构? 大量数据的有效管理机制。描述计算机算法的时候使用的数据结构有很多种:   数
数据结构是对在计算机内存中(有时候在磁盘中)的数据的一种安排。数据结构包括数组、链表、栈、二
Algorithms Table of Contents 1 Overview 1.1 Properties of algorithms 2 Algorithmic Paradigm 2
算法相关: 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示
离开算法谈数据结构是无法完全理解数据结构的。 算法定义 算法是解决特定问题求解步骤的描述,在计
机器学习算法中如何选取超参数:学习速率、正则项系数、minibatch size 本文是《Neural networks an
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号