你带酒来,我有故事

算法中描述复杂度的大O是什么意思?

:: 代码生涯 二十画生 524℃ 0评论

一、简介

算法是解决问题的方法,通常一个问题会有多种解决方法,就是有多种算法,那么我们如何决定哪个算法更好或者更高效呢?

为了描述一个算法的效率,就用到了这个大O,包括:

  1. O(n) 线性时间操作
  2. O(1) 常数时间操作
  3. O(log n) 对数时间操作

例如在 Redis 的文档中,对每个命令都会给出复杂度描述

算法中描述复杂度的大O是什么意思?

算法中描述复杂度的大O是什么意思?

明白大O的作用有助于我们提高程序的效率,下面看看他们的具体含义

二、O(n) 线性时间操作

假设有一个盒子,其中有多个印着数字的卡片(例如 1, 2, 3, 4, … 16)

现在我们被要求找出数字6的卡片,应该怎么做?

一次拿出一个卡片,看数字是否为6,如果符合,那就结束了,否则继续查看下一个卡片,最坏的情况是所有卡片都被检查了一遍

这种方式就是线性操作,记为 O(n)

三、O(1) 常数时间操作

假设有一个盒子,其中有数字(1, 2, 3, 4, … 16),在盒子外面写上盒子中有16个数字

当有人问我们盒子里有多少个数字的时候,我们看一眼盒子上的标记就可以马上告诉他有16个

这就是常数操作,记为 O(1)

四、O(log n) 对数时间操作

假设有一个盒子,其中有数字(1, 2, 3, 4, … 16),并且这些数字是排好序的

当有人要求找到数字16,以为有序,我们可以把这些数字分成两组,对符合范围的那个组继续拆开,这样,经过4步就可以找到 16

算法中描述复杂度的大O是什么意思?

16=2的4次方

算法中描述复杂度的大O是什么意思?

在比如有 64 个数字,找到 64 需要 6 步

算法中描述复杂度的大O是什么意思?

这就是指数型操作,记为 O(log n)

五、小结

算法中描述复杂度的大O是什么意思?

可以看到,O(1) 最牛,不管数据量有多大,都是一下就完成,O(n) 最惨,数据量大时就有的忙了,O(log n) 虽然与数据量成正比,但所需时间是指数型下降的,很不错

知道了大O的含义,我们也就可以更好的选择算法,例如 redis 中的 keys命令,他的复杂度是 O(n),我们就要慎用了

转载请注明:二十画生 » 算法中描述复杂度的大O是什么意思?

喜欢 (2)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址