AGe*_*eek 39 c algorithm asymptotic-complexity
我有一个问题,我试着一次又一次地思考它......但是没有得到什么,所以在这里发布问题.也许我可以得到一些其他人的观点,试着让它发挥作用......
问题是:我们得到一个SORTED数组,它由一组偶数发生的值组成,除了一个,发生ODD次数.我们需要在log n时间找到解决方案.
在O(n)时间内很容易找到解决方案,但在log n时间执行它看起来相当棘手.
use*_*751 29
定理:针对此问题的每个确定性算法在最坏的情况下探测？(log 2 n)内存位置.
证明(完全以更正式的方式重写):
令k> 0为奇数,并且令n = k 2.我们描述了一个强制(log 2(k + 1))2 =？(log 2 n)探针的对手.
我们称相同元素组的最大子序列.对手的可能输入包括k个长度为k的段 x 1 x 2 ... x k.对于每个段x j,存在整数b j？[0,k]使得x j由j-1 的b j个副本和j的j-k j个副本组成.每组最多重叠两个片段,每个片段最多重叠两个片段.
Group boundaries
| | | | |
0 0 1 1 1 2 2 3 3
| | | |
Segment boundaries
只要增加了两个,我们就按惯例假设一个双边界.
Group boundaries
| || | |
0 0 0 2 2 2 2 3 3
权利要求:第j的位置个组边界(？1焦耳k)的唯一地由段X确定Ĵ.
证明:这只是((j - 1)K + B之后Ĵ)个存储器位置,且x Ĵ唯一地决定了B Ĵ.//
我们说,该算法已观察到的第j 个组边界的情况下,x的其探测结果Ĵ唯一地确定x,Ĵ.按照惯例,始终遵守输入的开始和结束.算法可以在不观察组边界的情况下唯一地确定组边界的位置.
Group boundaries
| X | | |
0 0 ? 1 2 2 3 3 3
| | | |
Segment boundaries
只给出0 0 ?,算法无法确定是否？是一个0或1.然而,在上下文中,？必须是1,否则将有三个奇数组,并且可以推断出X处的组边界.这些推论对于对手来说可能是有问题的,但事实证明,只有在所讨论的群体边界"无关紧要"之后才能制作出来.
声明:在算法执行期间的任何给定点,考虑它已观察到的组边界集.恰好一个连续的对在奇数距离,奇数组在它们之间.
证明:每隔一对连续的边界甚至只限组.//
将由特殊连续对限定的奇数长度子序列定义为相关子序列.
声明:相关子序列内部的组边界没有唯一确定.如果存在至少一个这样的边界,那么奇数组的身份不是唯一确定的.
证明:在不失一般性的情况下,假设已经探测到不在相关子序列中的每个存储器位置,并且相关子序列中包含的每个段具有恰好一个未被探测的位置.假设第j 个组边界(称为B)在于相关序列的内部.根据假设,对x j的探测确定B的位置,直到两个连续的可能性.我们将距左侧观察到的边界奇数左边和另一个奇数右边的奇数距离称为一个.对于这两种可能性,我们从左到右工作并固定每个剩余内部组边界的位置,以使其左侧的组是偶数.(我们可以这样做,因为它们每个都有两个连续的可能性.)如果B在奇数左边,那么它左边的组是唯一的奇数组.如果B在奇数右边,那么相关子序列中的最后一个组是唯一的奇数组.两者都是有效输入,因此算法既不确定B的位置也不确定奇数组.//
例:
Observed group boundaries; relevant subsequence marked by […]
[ ] |
0 0 Y 1 1 Z 2 3 3
| | | |
Segment boundaries
Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1
作为这种说法的结果,算法无论如何工作,都必须将相关的子序列缩小到一个组.因此,根据定义,它必须遵守一些群体界限.对手现在的任务是尽可能多地保持开放.
在算法执行期间的任何给定点,攻击者在内部致力于相关子序列之外的每个存储器位置的一种可能性.一开始,相关的子序列是整个输入,因此没有初始承诺.每当算法探测x j的未提交位置时,攻击者必须提交两个值之一:j - 1或j.如果它可以避免让第j 个边界被观察到,那么它会选择一个至少留下一半剩余可能性的值(就观察而言).否则,它选择使至少一半的组保持在相关的时间间隔内并为其他组提交值.
以这种方式,攻击迫使算法来观察至少登录2(K + 1)组的边界,并且在观察第j 个组边界,该算法被强制使至少登录2(K + 1)的探针.
扩展:
该结果通过随机化输入直接扩展到随机算法,将"至少减半"(从算法的角度来看)替换为"最好在期望值减半",并应用标准浓度不等式.
它还延伸到没有任何组可以大于副本的情况; 在这种情况下,下限是？(log n log s).
Nab*_*abb 15
排序数组表示二进制搜索.我们必须重新定义平等和比较.平等简单意味着奇数个元素.我们可以通过观察组的第一个或最后一个元素的索引来进行比较.第一个元素是奇数组之前的偶数索引(从0开始),奇数组之后是奇数索引.我们可以使用二进制搜索找到组的第一个和最后一个元素.总成本为O((log N)²).
证明O((log N)²)
T(2) = 1 //to make the summation nice
T(N) = log(N) + T(N/2) //log(N) is finding the first/last elements
对于一些N = 2 ^ k,
T(2^k) = (log 2^k) + T(2^(k-1))
= (log 2^k) + (log 2^(k-1)) + T(2^(k-2))
= (log 2^k) + (log 2^(k-1)) + (log 2^(k-2)) + ... + (log 2^2) + 1
= k + (k-1) + (k-2) + ... + 1
= k(k+1)/2
= (k² + k)/2
= (log(N)² + log(N))/ 2
= O(log(N)²)
Dim*_*eou 10
查看数组的中间元素.通过几个适当的二进制搜索,您可以在数组中找到第一个和最后一个外观.例如,如果中间元素是'a',则需要查找i并j如下所示:
[* * * * a a a a * * *]
^ ^
| |
| |
i j
是j - i偶数吗？你完成了!否则(这是这里的关键),要问的问题是我是偶数还是奇数？你看到这条知识意味着什么吗？其余的很容易.
这个答案是为了支持"throwawayacct"发布的答案.他值得赏金.我花了一些时间在这个问题上,我完全相信他的证明是正确的,你需要Ω(log(n)^ 2)个查询来查找出现奇数次的数字.我确信,因为我只是在略过他的解决方案之后重新创建完全相同的论点.
在该解决方案中,攻击者创建输入以使算法难以生存,但对于人类分析器而言也很简单.输入由k个页面组成,每个页面都有k个条目.条目总数是n = k ^ 2,重要的是O(log(k))= O(log(n))和Ω(log(k))=Ω(log(n)).为了进行输入,对手制作一个长度为k的形式为00 ... 011 ... 1的字符串,其中过渡处于任意位置.然后将字符串中的每个符号扩展为aa ... abb ... b形式的长度为k的页面,其中在第i页上,a = i且b = i + 1.每个页面上的转换也处于任意位置,除了奇偶校验与页面扩展的符号一致.
理解分析算法最坏情况的"对手方法"非常重要.攻击者回答关于算法输入的查询,而不承诺将来的答案.答案必须保持一致,并且当对手被固定到足以使算法得出结论时游戏结束.
有了这样的背景,这里有一些观察:
1)如果要通过在该页面中进行查询来学习页面中转换的奇偶校验,则必须了解转换的确切位置,并且需要Ω(log(k))查询.任何查询集合都将转换点限制为一个间隔,任何长度大于1的间隔都具有两个奇偶校验.在该页面中最有效地搜索转换是二进制搜索.
2)最微妙和最重要的一点:有两种方法可以确定特定页面内转换的奇偶校验.您可以在该页面中进行足够的查询以查找转换,或者如果在较早和较晚的页面中找到相同的奇偶校验,则可以推断奇偶校验.无论如何都没有逃脱.任何查询集都会将每个页面中的转换点限制为某个时间间隔.对奇偶校验的唯一限制来自长度为1的区间.否则,过渡点可以自由地摆动以具有任何一致的奇偶校验.
3)在对手方法中,没有幸运的罢工.例如,假设您在某个页面中的第一个查询是朝向一端而不是中间.由于对手没有答应,他可以自由地将过渡放在长边.
4)最终结果是您被迫直接探测Ω(log(k))页面中的奇偶校验,并且每个子问题的工作也是Ω(log(k)).
5)随机选择的事情并不比对抗选择好得多.数学更复杂,因为现在你可以得到部分统计信息,而不是严格的是你知道一个奇偶校验或不知道它.但它没什么区别.例如,您可以给每个页面长度k ^ 2,因此很有可能,每个页面中的第一个log(k)查询几乎不会告诉您该页面中的奇偶校验.对手可以在开始时做出随机选择,它仍然有效.
从数组的中间开始向后走,直到得到一个与中心值不同的值.检查该边界上方的数字是否为奇数或偶数索引.如果它是奇数,那么出现奇数次的数字是在左边,所以在你找到的开头和边界之间重复搜索.如果它是偶数,那么出现奇数次的数字必须在数组中稍后,所以在右半部分重复搜索.
如上所述,这具有对数和线性分量.如果你想保持整个事情对数,而不是仅仅通过数组倒着走路,为不同的值,你要使用二进制搜索来代替.除非你想到许多相同数字的重复,二进制搜索可能不值得虽然.