数据API 产品矩阵 案例 关于
掌握聚合最新动态了解行业最新趋势
API接口,开发服务,免费咨询服务

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

简介

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

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

  1. O(n) 线性时间操作

  2. O(1) 常数时间操作

  3. O(log n) 对数时间操作

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

明白大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

1675-640.jpg.jpg

16=2的4次方

1676-640.jpg.jpg

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

未命名1496721336.png

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

小结

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

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

原文来自:性能与架构

声明:所有来源为“聚合数据”的内容信息,未经本网许可,不得转载!如对内容有异议或投诉,请与我们联系。邮箱:marketing@think-land.com

掌握聚合最新动态了解行业最新趋势
API接口,开发服务,免费咨询服务
算法中描述复杂度的大O是什么意思?
发布:2017-06-06 11:51:07

简介

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

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

  1. O(n) 线性时间操作

  2. O(1) 常数时间操作

  3. O(log n) 对数时间操作

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

明白大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

1675-640.jpg.jpg

16=2的4次方

1676-640.jpg.jpg

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

未命名1496721336.png

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

小结

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

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

原文来自:性能与架构

声明:所有来源为“聚合数据”的内容信息,未经本网许可,不得转载!如对内容有异议或投诉,请与我们联系。邮箱:marketing@think-land.com

选择想要的接口, 看看能免费获取多少次调用 选择(单选)或填写想要的接口
  • 短信API服务
  • 银行卡四元素检测[简]
  • 身份证实名认证
  • 手机状态查询
  • 三网手机实名制认证[简]
  • 身份证OCR识别
  • 证件识别
  • 企业工商信息
短信API服务
  • 短信API服务
  • 银行卡四元素检测[简]
  • 身份证实名认证
  • 手机状态查询
  • 三网手机实名制认证[简]
  • 身份证OCR识别
  • 证件识别
  • 企业工商信息
  • 确定
选择您的身份
请选择寻找接口的目的
预计每月调用量
请选择预计每月调用量
产品研发的阶段
请选择产品研发的阶段
×

前往领取
电话 0512-88869195
×
企业用户认证,
可获得1000次免费调用
注册登录 > 企业账户认证 > 领取接口包
企业用户认证领取接口包 立即领取
× 企业用户认证,
可获得1000次免费调用,立即领取>
数 据 驱 动 未 来
Data Drives The Future