精华内容
下载资源
问答
  • 大O表示法

    2020-03-04 16:00:32
    大O表示法???这是什么东西?? 大O表示法其实并没有多么高大上,而是一种特殊的表示法,指出了算法的速度有多快。这种表示法简单易懂,非常明了,所以应用广泛。 举个例子,就如我上一篇介绍二分查找的博客中...

    大O表示法???这是什么东西??

    大O表示法其实并没有多么高大上,而是一种特殊的表示法,指出了算法的速度有多快。这种表示法简单易懂,非常明了,所以应用广泛。

    举个例子,就如我上一篇博客中提到的二分查找(https://blog.csdn.net/qq_45835827/article/details/104651718)。如果用大O表示法来分别表示简单查找和二分查找的速度为:
    简单查找:O(n)
    二分查找:O(log2n)
    这就是大O表示法,前面的O有点大。

    因为在很多时候,如果只是告诉你算法花了多长时间是没有用的,而是需要知道运行时间如何随list的增长而增长。大O表示法的用武之地就在于此。也就是之前所说的,大O表示法指出了算法的速度有多快。

    下面给大家介绍一些常见的大O运行时间

    • O(log2n),对数时间,例如:二分查找。
    • O(log n),线性时间,例如:简单查找。
    • O(n * log2n),例如:快速排序(可以参考我的另外一篇博客)。
    • O(log n2)例如:选择排序(可以参考我的另外一篇博客)。
    • O(log n!)例如:用于旅行商问题。

    大家可能也注意到了一点,大O表示法指出了最糟情况下的运行时间。怎么去理解这个性质呢?其实就是说该算法最糟运行的时间大O表示法所指代的时间,这是一个保证。比如说,小明心里想的数字为50,结果大红一次就猜中了,这就是最佳情况。所以还应考虑平均情况(在我后面的博客有介绍)。

    另外,在实际的应用中,我们很难将运行时间直接转换为操作数(即大O后面括号里表示的速度)。前面介绍的都是比较简单的例子供大家参考理解。

    最后归纳总结一下从大O表示法中获得的理解。

    • 算法的速度并非指的时间,而是操作数的增速
    • 谈论算法的速度的时候,我们指的是随着输入的增加,其运行时间将以什么样的速度增加
    • 算法的运行时间用大O表示法表示
    • 当搜索的元素越多的时候,算法速度的比较就越明显
    • 算法的运行时间不以秒为单位,而是从其增速的角度来度量的

    本博客所有内容均整理自《算法图鉴》,这篇博客也作为自己的学习笔记,欢迎大家交流讨论。

    展开全文
  • 大O表示法

    2019-09-25 14:06:51
    大O表示法是一种特殊的表示法,指出了算法的速度有多快。当然是趋向于操作的次数,因为每种操作的方式不同所需的时间也就无法统一。大O表示法通常作为一个算法优劣的标准,越快越好,数值越小越快。 二、大O表示...

    一、大O表示法定义

    大O表示法是一种特殊的表示法,指出了算法的速度有多快。当然是趋向于操作的次数,因为每种操作的方式不同所需的时间也就无法统一。大O表示法通常作为一个算法优劣的标准,越快越好,数值越小越快。

     

    二、大O表示法语法

    O(n)

    例:

    假设列表有n个元素,简单查找需要查找每个元素,因此需要执行n次操作。使用大O表示法记做:O(n)

    如果用二分法查找,则需要执行 log 2次操作。使用大O表示法记做:O(log 2n)

     

    三、理解大O表示法

    大O表示法记录的是最糟糕情况下的运行次数。

    从上面可以看到简单查找记做:O(n)

    架设n=100,查找1时实际才执行1次,查找100时,n才等于100。同样记做:O(100)

    同样用二分法在1~100查找50时则只需执行一次,在最糟糕的情况下才执行7次数,同样记做:O(log 2100)

     

    四、一些常见的大O运行时间

    O(log n),也叫对数时间,这样的算法包括二分查找。

    O(n),也叫线性时间,这样的算法包括简单查找。

    O(n*log n),这样的算法包括快速排序算法,较快。

    O(n2),这样的算法包括选择排序算法,较慢。

    O(n!),读作O n的阶乘次,这样的算法包括旅行商算法,一种非常慢的算法。

     

    转载于:https://www.cnblogs.com/zeussbook/p/11129655.html

    展开全文
  • 大O 表示法

    2019-05-30 09:46:00
    大O表示法 指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法...

    大O表示法

    指出了算法有多快。例如,假设列表包含n个元素。简
    单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,
    这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法
    让你能够比较操作数,它指出了算法运行时间的增速。

     

    大O 表示法指出了最糟情况下的运行时间
    假设你使用简单查找在电话簿中找人。你知道,简单查找的运行时间为O(n),这意味着在最
    糟情况下,必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人,一次
    就能找到,无需查看每个条目。考虑到一次就找到了Adit,请问这种算法的运行时间是O(n)还是
    O(1)呢?
    简单查找的运行时间总是为O(n)。查找Adit时,一次就找到了,这是最佳的情形,但大O表
    示法说的是最糟的情形。因此,你可以说,在最糟情况下,必须查看电话簿中的每个条目,对应
    的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

     

    下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

     O(log n),也叫对数时间,这样的算法包括二分查找。
     O(n),也叫线性时间,这样的算法包括简单查找。
     O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
     O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
     O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

     

    小结

     二分查找的速度比简单查找快得多。

     O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。
     算法运行时间并不以秒为单位。
     算法运行时间是从其增速的角度度量的。
     算法运行时间用大O表示法表示。

    转载于:https://www.cnblogs.com/pickKnow/p/10947798.html

    展开全文
  • O 表示法

    2019-05-22 18:08:00
    大O表示法是一种特殊的表示法,指出了算法的速度有多快。谁在乎呢? 实际上,你经常要 使用别人编写的算法,在这种情况下,知道这些算法的速度大有裨益。 一些常见的大 O 运行时间: O(log n),也叫对数...

    大 O 表示法


     

    定义

    • 大O表示法是一种特殊的表示法,指出了算法的速度有多快。谁在乎呢?
    • 实际上,你经常要 使用别人编写的算法,在这种情况下,知道这些算法的速度大有裨益。

     

    一些常见的大 O 运行时间:

    • O(log n),也叫对数时间,这样的算法包括二分查找
    • O(n),也叫线性时间,这样的算法包括简单查
    • O(n * log n),对数与线性结合——一种速度较快的排序算法
    • O(?^2 ),这样的算法主要针对选择排序——一种速度较慢的排序算法
    • O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法

     图解:


     

    启示录:

    1. 算法的速度指的并非时间,而是操作数的增速。
    2. 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。
    3. 算法的运行时间用大O表示法表示。
    4. O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。

     

     

     P.S : 本文学习《算法图解》,如有雷同或不适之处,望读者指出,并与笔者私信联系,谢谢!

     

    转载于:https://www.cnblogs.com/harp-yestar/p/BigO.html

    展开全文
  • 大o表示法

    2019-04-08 19:26:37
    O(1)— 常量时间:给定一个大小为n的输入,概算法只需要一步就可以完成任务。 O(log n)— 对数时间:给定大小为n的输入,该算法每执行一步,它完成任务所需要的步骤数目会以一定的因子减少。 O(n)— 线性时间:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,205
精华内容 882
关键字:

大o表示法