专栏首页代码洁癖患者【译】大O的友好指南

【译】大O的友好指南

原文链接:https://medium.com/@daily_javascript/a-friendly-guide-to-big-o-ea781c5f68f0

算法复杂度

并不是每个公司在面试的时候都会问关于算法复杂度大O的问题,但是如果你想要到Facebook、Google或Amazon这样的公司工作的话,这是你必须要了解的知识。如果你没有很好的数学功底,那么你去看课本上关于大O的概念的话将会是一场灾难。

Let T(n) = the number of operations performed in an algorithm as a function of n. 
T(n) = O(f(n)) if and only if there exists two constants, n0 > 0 and c > 0, and a function f(n) such that for all n > n0, cf(n) ≥ T(n).

那么我们就一起来学习一下它的数学证明吧。开个玩笑,实际上证明要比概念复杂得多(译者:不会就直说嘛)。

回想一下,你是否曾经接受过这样的任务,为了完成它,你需要按照指定的步骤,一步一步来执行。在计算机科学中,这一系列指定的步骤被称为算法。

在现实生活中,我们为了完成一项任务,往往会寻找更好的办法:更快、更便宜、或者更明确的方法。算法也是一样,我们常常需要更好的算法来实现。但是我们怎么知道哪种算法对计算机而言是更好的呢?

一个比较直观的方法就是,选择不同算法之中,完成同一项任务用时最短的那个,也就是我们常说的运行时间最短的。不幸的是,我们没有办法精确的比较出哪个算法的运行时间更短,因为它受很多因素的影响。

例如:

  • 写算法所用的语言
  • 相同语言的版本差异
  • 计算机硬件差异,每次读取数据的大小

我们能做的是通过计算算法从开始到完成一共做了多少步工作来近似的比较两个算法的运行时间。所以我们应该做出一些假设,而不管每个人使用的硬件和语言的差异,找到一个公认的方法来比较不同算法解决问题的能力。

假设1:

计算机每次从上到下读取一个步骤

假设2:

定义变量、调用函数、逻辑对比以及所有的算术运算都被当成一个步骤

假设3:

内存是无限大的,而且访问任何位置的数据所消耗的时间是一样的

做出了上面的假设之后,我们来看一个简单的例子:

function m(a, b) {
    ans = 1

    while(b > 0) {
        ans = ans * a
        b = b - 1
    }
    return ans
}

这个算法先定义了一个变量,这是一个步骤;然后开始了循环,这是三步(比较、乘法、减法)。最后返回变量,这也是一个步骤。所以这个算法的总步骤就是

2 + (3 * b)

如果b=100,这个算法就要进行302步,

如果b=1000,这个算法就要进行3002步,

如果b=10,000,这个算法就要进行30,002步。

可以看到,由于我们不需要精确的比较,所以数字2对结果的影响微乎其微。这就是为什么当我们计算大O的时候,你只需要关心影响最大的因素,而可以忽略常数以及影响较小的因素。我们再来看一个例子:

x + x^2 + x^3

你可以放心的忽略掉x和x2,因为它们没有x3对结果的影响大。

大O只是用来判断运行时间增加的速率,也叫作渐近分析。

所以我们已经知道了如何计算大O,但是我们怎么知道要选择哪些影响因素呢?我们需要尽可能大的输入,来忽略常数和低阶因素。大O表示的是最坏情况,这才是最有意义的比较结果。

PS:我的博客支持评论功能啦!小伙伴们有什么想法可以点击阅读原文,到对应的文章下面留言。

本文分享自微信公众号 - 代码洁癖患者(Jackeyzhe2018),作者:Jackeyzhe

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【译】Googler如何解决编程问题

    本文是Google工程师Steve Merritt的一篇博客,向大家介绍他自己和身边的同事解决编程问题的方法。

    Jackeyzhe
  • Redis命令详解:Streams

    Redis5.0迎来了一种新的数据结构Streams,没有了解过的同学可以先阅读前文,今天来介绍一下Streams相关的命令。

    Jackeyzhe
  • Redis命令详解:Strings

    String类型是Redis中比较常用的类型,因此,和String相关的命令也比较多

    Jackeyzhe
  • 我们需要“算法天使”

    算法构筑了进入互联网的很多东西,这已经被不止一次地论述过。但是,还没有一些非常确凿的证据,可以支持当初创造更加以人为中心的算法解决方案的办法。比如,我们是否需要...

    CSDN技术头条
  • 不懂算法,还想进大厂?做梦吧

    拿到题目后就开始想着怎么写代码,结果写了大半天,发现越写越乱,最后就写不下去了,又或者是,看到题目后,一脸懵逼,完全不知道怎么下手。

    Java团长
  • 腾讯10年的架构师的算法学习经验分享

    拿到题目后就开始想着怎么写代码,结果写了大半天,发现越写越乱,最后就写不下去了,又或者是,看到题目后,一脸懵逼,完全不知道怎么下手。

    乔戈里
  • 腾讯十年大佬总结的算法学习经验

    拿到题目后就开始想着怎么写代码,结果写了大半天,发现越写越乱,最后就写不下去了,又或者是,看到题目后,一脸懵逼,完全不知道怎么下手。

    帅地
  • 不懂算法,还想进大厂?做梦吧

    拿到题目后就开始想着怎么写代码,结果写了大半天,发现越写越乱,最后就写不下去了,又或者是,看到题目后,一脸懵逼,完全不知道怎么下手。

    谭庆波
  • python人工智能学习路线

    高等数学是基础中的基础,一切理工科都需要这个打底,数据挖掘、人工智能、模式识别此类跟数据打交道的又尤其需要多元微积分运算基础、线性代数很重要,一般...

    python学习教程
  • 快速学习-系统算法详解(基于人口统计学的推荐算法)

    cwl_java

扫码关注云+社区

领取腾讯云代金券