`
liss
  • 浏览: 844196 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

大O表示法是什么?

阅读更多

  称一个函数g(n)是O(f(n)),当且仅当存在常数c>0和n0>=0,对一切n>n0均有|g(n)|<=c|f(n)|成立,也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。

  定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数。T(n)称为这一算法的"时间复杂度"。当输入量n逐渐加大时,时间复杂度的极限情形称为算法的"渐近时间复杂度"。

  我们常用大O表示法表示时间复杂度,注意它是某一个算法的时间复杂度。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。此外,一个问题本身也有它的复杂度,如果某个算法的复杂度到达了这个问题复杂度的下界,那就称这样的算法是最佳算法。

  通常我们需要一种方法来对不同的算法来进行比较,一般来说,解决同样的问题有多种算法,那么在不同的客观条件下如何对不同的算法进行取舍呢?

一,算法的目标

  1,容易理解,编码和调试

  优秀的算法通常是简洁而清晰的,这样带来的直接好处就是易于编码和理解,同时这样算法也必定是健壮的,如果一个算法晦涩难懂,则很可能其中会隐藏较多的错误。

  2,最小的代价

  算法的代价的最小化是指其执行时间最短且占用的存储空间最少,它们之间 往往是相互矛盾的,然而一般而言,算法的执行时间是主要的评价标准。

二,算法的执行时间

  算法的执行时间等于它所有基本操作执行时间之和, 而一条基本操作的执行时间等于它执行的次数和每一次执行的时间的积,

  如下:

  算法的执行时间 = 操作1 + 操作2 + ... + 操作n

  操作的执行时间 = 操作执行次数 X 执行一次的时间

  然而存在一个问题,不同的编程语言,不同的编译器,或不同的CPU等因素将导致执行一次操作的时间各不相同,这样的结果会使算法的比较产生歧义, 于是我们假定所有计算机执行相同的一次基本操作所需时间相同,而把算法中基本操作所执行的最大次数作为量度。就是说我们把算法的执行时间简单地用基本操作的执行次数来代替了。

  那么除此之外,基本操作是什么? 它可以是基本运算,赋值,比较,交换等,如在排序中,基本操作指的是元素的比较及交换。而在线性查找中,它是数据的比较。

三,时间复杂度和大O表示法

  当问题规模即要处理的数据增长时, 基本操作要重复执行的次数必定也会增长, 那么我们关心地是这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。这个所谓的数量级就称为算法的渐近时间复杂度(asymptotic time complexity), 简称为时间复杂度。如何分析这个数量级呢? 由于基本操作的执行次数是问题规模n 的一个函数T(n), 所以问题就是我们要确定这个函数T(n)是什么, 然后分析它的数量级, 拥有相同数量级的函数 f(n) 的集合表示为 O(f(n)), O是数量级的标记。如果T(n)的数量级和f(n)相同,

  显然T(n) ∈ Of(n)。这个函数的值表示当我要处理的数据量增长时,基本操作执行次数以什么样的比例增长。即n增长时,T(n)增长多少?

四,几个例子

  比如说一个冒泡排序的算法, 假如有10个数,第一次循环比较9次,第二次循环比较8次,以此类推,一共

  循环9次,那么总次数为 9+8+7+6+5+4+3+2+1 等于45次,则对于N个数来说, 总比较次数为 N(N-1)/2 次,

  可见得对于N个数来说, 它的比较次数的数量级已达到N的平方, 即 T = N(N-1)/2 ,则我们说它的比较操作的

  时间复杂度为 O(n2) (n的平方)。

  另外对于一个数组的线性查找呢? 很显然, 在最坏的情况下,10个数要比较10次,那么对于N个数来说,

  要比较N次, 平均 N/2 次, 即 T = N/2 , 它的数量级是一次的,则我们说这个线性查找的时间复杂度是线性的,

  即 O(n).

五,拓展

  定义一:Θ(g(n))={f(n) | 如果存在正常数c1、c2和正整数n0,使得当n>=n0时,0<c1g(n)<=f(n)<=c2g(n)恒成立}

  定义二:Ο(g(n))={f(n) | 如果存在正常数c和正整数n0,使得当n>=n0时,0<=f(n)<=cg(n)恒成立}

  定义三:Ω(g(n))={f(n) | 如果存在正常数c和正整数n0,使得当n>=n0时,0<=cg(n)<=f(n)恒成立}

分享到:
评论

相关推荐

    时间复杂度和空间复杂度,大O表示法【数据结构和算法入门2】

    时间复杂度和空间复杂度,大O表示法【数据结构和算法入门2】

    大O表示法与算法复杂度分析:深入理解与应用指南

    本文详细介绍了大O表示法及其在算法复杂度分析中的应用,包括算法复杂度的重要性、大O表示法的基本概念和分类、如何使用大O表示法进行复杂度分析,以及代码示例。希望这能帮助读者更好地理解和应用大O表示法,提高...

    大O表示法复杂度速查表

    大O表示法复杂度速查表 包括搜索、排序、图、堆算法及各种数据结构的大O复杂度表示法。

    [2.2.1]--202)大O表示法.srt

    [2.2.1]--202)大O表示法.srt

    《Java数据结构和算法》学习笔记(1)——数组 二分法 大O表示法

    本文将深入探讨《Java数据结构和算法》学习笔记的第一部分,主要聚焦于数组、二分法以及大O表示法。这些基础知识对于提升代码性能和优化解决方案具有决定性的作用。 **数组**是编程中最基本的数据结构之一,它在...

    最小表示法,周源ppt

    最小表示法是一种在字符串处理和算法竞赛中不太常见但非常经典的思想,主要用于解决字符串的循环同构问题。在本文中,我们将深入探讨最小表示法及其在解决特定问题上的应用。 循环同构指的是两个字符串可以通过有限...

    Coursera课程:数据结构与算法(UCSD)模块1第二周Python答案(大O表示法,斐波拉契数列,最大公约数代码)

    课程链接:... week2小测答案:大O表示法,函数增长率3. week2编程作业答案:斐波拉契数列(求值、求个位数、求和、求平方和),最大公约数,最小公倍数以上均为Python解法

    鸟哥的 Linux 私房菜第12章-正规表示法与文件格式化处理1

    `grep`命令除了基础的搜索功能外,还有许多进阶选项,如`-i`忽略大小写,`-v`反向选择,`-o`只输出匹配部分,`-E`启用扩展正规表示法等。这些选项结合正规表示法,能够更灵活地处理文本数据。 **sed 工具** `sed`是...

    三元组和十字链表表示法1

    当非零元素数量较大时,这种表示法可能效率较低。 **十字链表表示法**: 十字链表(Cross List)是另一种存储稀疏矩阵的方式,尤其适用于非零元素的位置和数量在操作中变化较大的情况。每个非零元素节点包含四个域...

    图的邻接表表示法 pdf

    图的邻接表表示法是一种数据结构,用于在计算机中存储和管理图的数据。图是由顶点(节点)和边组成的非线性结构。在邻接表表示法中,图的每个顶点都关联一个链表,链表中的每个结点代表与该顶点直接相连的其他顶点。...

    最小表示法在字符串循环同构问题中的应用PPT学习教案.pptx

    "最小表示法在字符串循环同构问题中的应用PPT学习教案" 本资源是关于字符串循环同构问题的学习教案,介绍了最小表示法在解决该问题中的应用。该资源共39页,涵盖了循环同构的定义、枚举算法、匹配算法、KMP算法等...

    Java常用算法手册

    1.大O表示法:粗略的量度方法即算法的速度是如何与数据项的个数相关的 算法 大O表示法表示的运行时间 线性查找 O(N) 二分查找 O(logN) 无序数组的插入 O(1) 有序数组的插入 O(N) 无序数组的删除 O(N) 有序...

    算法合集之浅析最小表示法思想在字符串循环同构问题中的应用PPT学习教案.pptx

    本资源是关于字符串循环同构问题的算法合集学习教案,主要讲解了如何使用最小表示法思想来解决字符串循环同构问题。通过对问题的分析和解释,学习者可以了解如何使用最小表示法思想来解决问题,并且可以了解枚举算法...

    C语言FAQ 常见问题列表

    o 2.2 64 位机上的 64 位类型是什么样的? o 2.3 怎样定义和声明全局变量和函数最好? o 2.4 extern 在函数声明中是什么意思? o 2.5 关键字 auto 到底有什么用途? o 2.6 我似乎不能成功定义一个链表。我试过 ...

    最大子段和问题 蛮力法 分治法 动态规划法

    分治法通常用于处理复杂的问题,通过将大问题分解成小问题来解决。在最大子段和问题上,我们可以尝试将数组分为两部分,然后分别找出左半部分、右半部分以及跨越整个数组的最大子段和。然而,分治法并不适用于这个...

    big_o_ref:使用 Meteor 构建的大型 O 符号参考应用程序

    Big O Notation 参考应用...来自应用程序创建者的报价使用 Big O Notation Reference App 可以减少您对理解大 O 表示法的挫败感如何开始前往或下载应用程序(即将推出)。 选择您想了解更多的大 O 订单。 获取知识。

    MovieBST:在电影收视率数据集上实现了二进制搜索树,并使用Big-O表示法分析了运行时

    在本项目“MovieBST”中,开发者利用C++语言实现了一个基于电影收视率数据集的BST,并对其运行时性能进行了分析,使用了大O表示法(Big-O notation)来描述算法的时间复杂性。 首先,我们需要了解二进制搜索树的...

    g2o资源包,官网下载

    g2o支持多种优化算法,包括Levenberg-Marquardt法、Gauss-Newton法以及更高效的二阶锥规划(Quadratic Programming)方法,这些算法都能在保持计算效率的同时,保证优化的精度。 在实际应用中,g2o常与其他图像识别...

    JAVA面试宝典

    《JAVA面试宝典》是一份涵盖了Java编程语言面试中常见问题及答案的资料,适合求职者在... Big-O表示法用于描述算法性能随输入规模增长的变化趋势。例如,O(1)表示常数时间,O(n)表示线性时间,O(log n)表示对数时间等。

    数据结构和算法德国大学课件

    #### O-Notation(大O表示法) - **定义**: - 大O表示法是用来描述算法运行时间上界的一种记号。它提供了一个算法在最坏情况下的运行时间的上界。 - 如果我们有一个函数`g(n)`,我们说`g(n) = O(n^k)`,意味着...

Global site tag (gtag.js) - Google Analytics