use*_*352 101 algorithm big-o logarithm time-complexity
我对big-O的了解是有限的,当日志术语出现在等式中时,它会让我更加惊讶.
有人可以用简单的语言向我解释O(log n)算法是什么吗？对数来自哪里？
当我试图解决这个中期练习题时,这个问题就出现了:
设X(1..n)和Y(1..n)包含两个整数列表,每个整数按非递减顺序排序.给出O(log n)-time算法以找到所有2n个组合元素的中值(或第n个最小整数).例如,X =(4,5,7,8,9)和Y =(3,5,8,9,10),那么7是组合列表的中位数(3,4,5,5,7) ,8,8,9,9,10).[提示:使用二分搜索的概念]
tem*_*def 280
我必须同意,第一次看到O(log n)算法时,这很奇怪......这个对数来自何处？但是,事实证明,有几种不同的方法可以让日志术语以big-O表示法显示.以下是一些:
拿任何数字n; 比方说,16.在得到小于或等于1的数字之前,你可以将n除以2的次数？对于16岁,我们有
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
请注意,这最终需要完成四个步骤.有趣的是,我们还有那个日志2 16 = 4.嗯...... 128怎么样？
128 / 2 = 64
64 / 2 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
这需要七个步骤,并记录2 128 = 7.这是巧合吗？不!这是有充分理由的.假设我们将数n除以2次i次.然后我们得到数字n/2 i.如果我们想要求解这个值最多为1的i的值,我们得到
N/2 我 ≤1
N≤2 我
日志2 N≤我
换句话说,如果我们选择我整数,使得I≥日志2 n,则除以n的一半了i次后,我们将有一个值,该值至多为1.我指此保证最小的大致登录2 n,所以如果我们有一个除以2的算法直到数字变得足够小,那么我们就可以说它终止于O(log n)步骤.
一个重要的细节是,你将n除以的是什么常数并不重要(只要它大于1); 如果除以常数k,则需要log k n步才能达到1.因此,任何重复将输入大小除以某个分数的算法都需要O(log n)次迭代才能终止.那些迭代可能需要花费很多时间,因此净运行时不必是O(log n),但步数将是对数的.
那么这会出现在哪里？一个典型的例子是二进制搜索,这是一种快速算法,用于搜索排序数组中的值.该算法的工作方式如下:
例如,要在数组中搜索5
1 3 5 7 9 11 13
我们先来看看中间元素:
1 3 5 7 9 11 13
^
从7> 5开始,由于数组已经排序,我们知道数字5不能在数组的后半部分,所以我们可以丢弃它.这离开了
1 3 5
所以现在我们来看看这里的中间元素:
1 3 5
^
由于3 <5,我们知道5不能出现在数组的前半部分,所以我们可以抛出前半部分数组离开
5
我们再次看一下这个数组的中间部分:
5
^
由于这正是我们正在寻找的数字,我们可以报告5确实在数组中.
那么效率如何呢？好吧,在每次迭代中,我们丢弃了至少一半剩余的数组元素.一旦数组为空或我们找到我们想要的值,算法就会停止.在最坏的情况下,元素不存在,所以我们将数组的大小减半,直到元素耗尽为止.这需要多长时间？好吧,既然我们一遍又一遍地将数组切成两半,我们将在大多数O(log n)次迭代中完成,因为在运行之前我们不能将数组切割为O(log n)次的一半以上超出数组元素.
按照一般分治技术(将问题分解成碎片,解决这些碎片,然后将问题重新组合在一起)的算法往往会出于对数术语,因为同样的原因 - 你不能继续削减一些对象比O(log n)倍多一半.您可能希望将merge sort视为一个很好的例子.
基数为10的数字是多少位？好吧,如果数字中有k个数字,那么我们的最大数字是10 k的倍数.最大的k位数是999 ... 9,k次,这等于10 k + 1 - 1.因此,如果我们知道n中有k个数字,那么我们知道n的值是最多10 k + 1 - 1.如果我们想用n求解k,我们得到
n≤10k + 1 - 1
n +1≤10k + 1
log 10(n + 1)≤k+ 1
(log 10(n + 1)) - 1≤k
从中我们得到k大约是n的基数-10对数.换句话说,n中的位数是O(log n).
例如,让我们考虑添加两个太大而不适合机器字的大数字的复杂性.假设我们将这些数字表示在基数10中,我们将数字称为m和n.添加它们的一种方法是通过小学 - 学校方法 - 一次写出一位数字,然后从右到左工作.例如,要添加1337和2065,我们首先将数字写为
1 3 3 7
+ 2 0 6 5
==============
我们添加最后一位数字并带1:
1
1 3 3 7
+ 2 0 6 5
==============
2
然后我们添加倒数第二个("倒数第二个")数字并携带1:
1 1
1 3 3 7
+ 2 0 6 5
==============
0 2
接下来,我们添加倒数第三个("antepenultimate")数字:
1 1
1 3 3 7
+ 2 0 6 5
==============
4 0 2
最后,我们添加倒数第四个("preantepenultimate"......我爱英语)数字:
1 1
1 3 3 7
+ 2 0 6 5
==============
3 4 0 2
现在,我们做了多少工作？我们每个数字总共进行O(1)工作(即,一定量的工作),并且有需要处理的O(max {log n,log m})总数.这给出了总共O(max {log n,log m})的复杂度,因为我们需要访问两个数字中的每个数字.
许多算法在某些基础上一次只能处理一个数字,从而获得O(log n)项.一个典型的例子是基数排序,它一次对一个数字排序整数.有许多种基数排序,但它们通常在时间O(n log U)中运行,其中U是被排序的最大可能整数.这样做的原因是排序的每次传递花费O(n)时间,并且处理被排序的最大数字的每个O(log U)数字所需的总共O(log U)次迭代.许多高级算法,例如Gabow的最短路径算法或Ford-Fulkerson最大流算法的缩放版本,在其复杂性方面具有对数项,因为它们一次只能处理一个数字.
至于你关于如何解决这个问题的第二个问题,你可能想看看这个探讨更高级应用程序的相关问题.鉴于此处描述的问题的一般结构,当您知道结果中存在对数项时,您现在可以更好地了解如何思考问题,因此我建议您不要在给出答案之前查看答案.一些想法.
希望这可以帮助!
当我们谈论大哦描述时,我们通常谈论解决给定大小的问题所花费的时间.通常,对于简单的问题,这个大小只是以输入元素的数量为特征,并且通常称为n或N.(显然,这并不总是正确的 - 图形的问题通常以顶点数量为特征,V和边数E;但是现在,我们将讨论对象列表,列表中有N个对象.)
当且仅在以下情况下,我们说问题"是(N的某些功能)的大哦"
对于所有N>某个任意N_0,存在一些常数c,使得算法的运行时间小于常数c次(N的某个函数).
换句话说,不要考虑设置问题的"持续开销"很重要的小问题,考虑大问题.在考虑大问题时,(O的某些函数)的大哦意味着运行时间仍然总是小于函数的某些常数.总是.
简而言之,该函数是一个上限,直到一个常数因子.
因此,"log-n of log(n)"意味着与上述相同,除了"N的某些功能"被"log(n)"替换.
所以,你的问题告诉你考虑二元搜索,所以让我们考虑一下.假设您有一个按递增顺序排序的N个元素的列表.您想知道该列表中是否存在某个给定的数字.一种不是二分搜索的方法是只扫描列表中的每个元素,看看它是否是你的目标号码.你可能会很幸运,并在第一次尝试时找到它.但在最坏的情况下,你会检查N次.这不是二进制搜索,它不是log(N)的大哦,因为没有办法强制它进入我们在上面勾勒出的标准.
你可以选择那个任意常数为c = 10,如果你的列表中有N = 32个元素,你就可以了:10*log(32)= 50,它大于32的运行时间.但是如果N = 64 ,10*log(64)= 60,小于64的运行时间.你可以选择c = 100,或1000,或者gazillion,你仍然可以找到一些违反该要求的N. 换句话说,没有N_0.
但是,如果我们进行二分搜索,我们选择中间元素,并进行比较.然后我们扔出一半的数字,然后再次,再次,等等.如果您的N = 32,那么您只能执行约5次,即log(32).如果你的N = 64,那么你只能做6次左右等等.现在你可以选择那个任意常数c,这样就可以满足大N值的要求.
在所有这些背景下,O(log(N))通常意味着你有一些方法可以做一个简单的事情,它可以将你的问题大小减少一半.就像上面的二元搜索一样.一旦你将问题减半,你可以再次将它切成两半,一次又一次.但是,关键的是,你不能做的是一些预处理步骤需要比O(log(N))时间更长的时间.因此,例如,除非你能在O(log(N))时间找到一种方法,否则你不能将两个列表混合到一个大的列表中.
(注意:几乎总是,Log(N)表示log-base-two,这就是我上面假设的.)