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符号,我们需要了解恒定时间操作,线性时间操作和对数时间操作。
现在让我们一起来随着例子/问题来学习这些大O符号。
需要解决的问题:假设我们有一个包含数字或卡片的盒子(如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
}
亟待解决的问题:假设我们得到一盒数字(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;
}
需要解决的问题:假设我们有一个包含数字(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个数字列表中找到一个数字。
本文系外文翻译,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文系外文翻译,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。