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

相关文章

来自专栏深度学习之tensorflow实战篇

tensorflow载入数据的三种方式 之 TF生成数据的方法

Tensorflow数据读取有三种方式: Preloaded data: 预加载数据 Feeding: Python产生数据,再把数据喂给后端。 Reading...

3374

与机器学习算法有关的数据结构

可能你对经常使用的统计分类包中的功能不满足你的需求而感到不爽,或者你已经有了一个新的数据处理方法。所以,你决定改动现有封装好的算法,开始编写你自己的机器学习方法...

2347
来自专栏小樱的经验随笔

numpy用法小结

前言   个人感觉网上对numpy的总结感觉不够详尽细致,在这里我对numpy做个相对细致的小结吧,在数据分析与人工智能方面会有所涉及到的东西在这里都说说吧,也...

3034
来自专栏desperate633

[编程题] 双核处理分析代码

一种双核CPU的两个核能够同时的处理任务,现在有n个已知数据量的任务需要交给CPU处理,假设已知CPU的每个核1秒可以处理1kb,每个核同时只能处理一项任务。n...

584
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

35610
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

解析opencv中Box Filter的实现并提出进一步加速的方案(源码共享)。

  说明:本文所有算法的涉及到的优化均指在PC上进行的,对于其他构架是否合适未知,请自行试验。       Box Filter,最经典的一种领域操作,在无数...

3677
来自专栏专知

Python高效数据分析的8个技巧

【导读】不管是参加Kaggle比赛,还是开发一个深度学习应用,第一步总是数据分析,这篇文章介绍了8个使用Python进行数据分析的方法,不仅能够提升运行效率,还...

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

【Python环境】Python中的结构化数据分析利器-Pandas简介

Pandas是python的一个数据分析包,最初由AQR Capital Management于2008年4月开发,并于2009年底开源出来,目前由专注于Pyt...

26910
来自专栏磐创AI技术团队的专栏

Tensorflow从入门到精通(二):附代码实战

1.Tensor介绍 Tensor(张量)是Tensorflow中最重要的数据结构,用来表示Tensorflow程序中的所有数据。Tensor本是广泛应用在物...

2817
来自专栏贾志刚-OpenCV学堂

TensorFlow中的feed与fetch

TensorFlow中的feed与fetch 一:占位符(placeholder)与feed 当我们构建一个模型的时候,有时候我们需要在运行时候输入一些初始数...

3907

扫码关注云+社区