算法:大O符号解释

O(n),O(1),O(log n)等大O符号被用来表示算法的效率。在这篇文章中,你会找到每个大O符号的例子和解释。

本文旨在解释大O符号是简单的。大多数学生和程序员都理解O(n)和O(1),但是理解O(log n)却有点困难。我尽可能简单地解释三个基本的大O符号。

让我们来回顾一下。

什么是算法?

算法是用来完成特定操作或解决问题的方法。我们都知道,解决某个问题的方法不止一种,同样,可以用多个算法来解决一个给定的问题。

想象一个场景:如果有多个算法/步骤来解决问题,我们如何找到哪个更好或更有效?

为了表示算法的效率,使用O(n),O(1),O(log n)等大O符号。

常见的大O符号是:

  • O(n):线性时间操作。
  • O(1):恒定时间操作。
  • O(log n):对数时间操作。

为了理解大O符号,我们需要了解恒定时间操作,线性时间操作和对数时间操作。

现在让我们一起来随着例子/问题来学习这些大O符号。

O(n):线性时间操作

需要解决的问题:假设我们有一个包含数字或卡片的盒子(如1,2,3,4,... 16),我们被问到盒子里是否有数字6。我们需要做什么?

每次选择一个号码,并检查我们选择的号码是6(搜索的号码)。

如果我们挑选的号码与搜索的号码相符,那就很好。否则,我们需要从框中选择另一个号码。这种一次挑选一个数字并验证它是否一个接一个地匹配直到所有n个数字都被挑选出来的方法称为线性运算。这种搜索n个数字的方式表示为O(n)。如果找到的号码是最后一个号码(最坏的情况),我们就需要将这n个数字都挑选一遍。。

int n = 16;
int[] numbers = {11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10};
int numberToSearch = 16;
int find(int numberToSearch, int[] numbers) {
for (int i = 0; i < n; i++) {
    if (numbers[i] = numberToSearch)
        return i; //FOUND
}
return -1; //NOT FOUND
}

O(1):恒定时间操作

亟待解决的问题:假设我们得到一盒数字(1,2,3,4,... 16),并且在盒子外面印有“盒子包含16个数字”。你会被问到盒子里有多少个数字/项目。因为你知道这个盒子被标记为包含16个球,所以你回复说这个盒子包含了16个。如果另一个人第二天问你同样的问题,你可以通过查看盒子再次回答,即使你得到另一个盒子100数字,如果它有一个标签说,该盒子包含100个数字,你依旧可以通过查看盒子再次回答。这被称为恒定时间操作。它表示为O(1)。

int n = 16;
int[] numbers = {11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10};
int findSize(int[] numbers) {
     return numbers.length;
}

O(log n):对数时间操作

需要解决的问题:假设我们有一个包含数字(1,2,3,4,... 16)的框,并且所有的数字都是有序的。你被要求在框中找到一个数字16。这里的问题是数字是有序的。我们把这些数字分成两部分。这16个数字被分成两组,每组包含8个。

int n = 16;
int[] numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
int numberToSearch = 16;
int median = 16/2 = 8;
int[] split1 = {1,2,3,4,5,6,7,8};
int[] split2 = {9,10,11,12,13,14,15,16}

数字16大于分组中的最大元素,因此要搜索的数字将仅被一分为二继续寻找,分割将会一直继续直到数字的末尾或找到了待搜索的数字。

因此:

看上面的图片,我们可以在4个步骤中找到一个数字(在16个数字的列表中)。

这可以写成,

在数学中,如果n = 2x,则log2 n = x。 (请参考二进制对数)

因此16 = 24可以写成log2 16 = 4。

这可以写成log2 n,或简单地写成O(log n)。

因此,需要四个步骤来找到一个包含16个数字的盒子,每个步骤将盒子分成两部分(这也称为二分查找)。

int find(int[] numbers, int numberToSearch) {
        int left = 0;
        int right = numbers.length - 1;
       while (left <= right) {
          int mid = left + (right - left) / 2;
          if (numberToSearch < numbers[mid]){
              right = mid - 1;
          }
          else if (numberToSearch > numbers[mid]) { 
              left = mid + 1;
          }
          else {
              return mid; //NUMBER FOUND
          }
        }
        return -1; //NUMBER NOT FOUND
 }

我希望这很简单,或者至少容易理解!

另一个例子:

例如,如果我们有64个数字,那么找到一个数字的最大步数可以如下推导出来,

64 = 26(2的6次方),这可以写成log2 64 = 6。因此,最多需要6个步骤才能在64个数字列表中找到一个数字。

原文链接:https://dzone.com/articles/algorithms-asymptotic-notations-explained-simple

原文作者: Arun Chandrasekaran

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯NEXT学位

你需要知道的算法之基础篇

3807
来自专栏noteless

UML简单介绍-如何看懂UML(二)

你画了一个三角形说这是一个接口,我花了一个圆形,跟你讲这个是接口?这其中的问题不言而喻。

1062
来自专栏大数据文摘

数学菜鸟的AI学习攻略 | 数学符号轻松入门

2714
来自专栏机器之心

业界 | 探索Siri背后的技术:将逆文本标准化(ITN)转化为标签问题

2884
来自专栏大数据挖掘DT机器学习

非主流自然语言处理:大规模语料词库自动生成

一、前言   写这篇文时,突然想到一个问题,大家的词库都是从哪来的?   之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博...

52412
来自专栏章鱼的慢慢技术路

统计计算学生成绩类问题汇总

1514
来自专栏小L的魔法馆

第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--I-填空题

3335
来自专栏IT派

如何用Python检测视频真伪?

译者注:本文以一段自打24小时耳光的视频为例子,介绍了如何利用均值哈希算法来检查重复视频帧。以下是译文。

963
来自专栏Android机动车

数据结构学习笔记——算法

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表达一个或者多个步骤。

601
来自专栏数据结构与算法

求细胞个数

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 阵列  4  10 02...

2688

扫码关注云+社区