算法:大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 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

数据挖掘知识脉络与资源整理(七)–饼图

? ? 简介 饼图英文学名为Sector Graph, 有名Pie Graph。常用于统计学模块。2D饼图为圆形,手画时,常用圆规作图。 仅排列在工作表的一...

2697
来自专栏数据科学与人工智能

Python语言做数据探索教程

本文总结Python语言做数据探索的知识。 类似R语言做数据探索,利用Python语言做数据探索。 1 数据导入 2 数据类型变换 3 数据集变换 4 数据排序...

3525
来自专栏机器之心

教程 | 如何在Python中快速进行语料库搜索:近似最近邻算法

3074
来自专栏SpiritLing

CSS3 translate、transform、transition区别

translate:移动,     transform的一个方法               通过 translate() 方法,元素从其当前位置移动,根据给定...

3305
来自专栏帮你学MatLab

《Experiment with MATLAB》读书笔记(八)

读书笔记(八) 这是第八部分指数函数 复制代码即可运行 %% 指数函数与近似导数 a = 2; t = 0:.01:2; h = ...

27510
来自专栏老马寒门IT

02-移动端开发教程-CSS3新特性(中)

背景在CSS3中也得到很大程度的增强,比如背景图片尺寸、背景裁切区域、背景定位参照点、多重背景等。

2090
来自专栏吴小龙同學

Android之美化控件Shape

除了使用drawable这样的图片外,随着图片资源增多,程序也越来越大,今天我们自定义图形shape的方法。 1 2 3 4 5 6 7 8 9 10 11 1...

3646
来自专栏生信宝典

R包ggseqlogo 绘制seq logo图

在生物信息分析中,经常会做序列分析图(sequence logo),这里的序列指的是核苷酸(DNA/RNA链中)或氨基酸(在蛋白质序列中)。sequence l...

1373
来自专栏儿童编程

Python常用函数汇总(数据结构、文件类)

Python提供了大量处理各类数据结构(字符串、列表、元组、字典)及文件类(包括文件夹)的函数,为我们进行相关操作提供了极大的便利。

1361
来自专栏数据小魔方

excel数据分析库系列|抽样设计

今天开始跟大家分享excel数据分析库系列——抽样设计! 作为微软excel中一直以来隐藏的最深最上档次的功能组件,excel数据分析工具库需要用户手动调用并开...

3247

扫码关注云+社区