[mock]12月28日

假设我们有一个全局升序数组,这个数组长度unlimited
现在我们有一个全局的指针和一个目标target值,target和指针你不可见。但是有以下几个操作
bool istag();
void goright();
void goleft();
我们保证target一定存在。
一开始指针指向值为0的位置。
问题:
1.你能否找到这个target
2.请写出你的算法和计算时间复杂度。

下面是现场写的代码,基本思路是倍增。(如果不是倍增,比如每次回到原点再加一走,是N^2的。) 注意如果为了分析复杂度方便,可以不直接*2折返,可以先回到原点再*2走。

bool search() {
int step = 1;
while (true) {
for (int i = 0; i < step; i++) {
goLeft()
if (isTarget()) return true;
}
step *= 2;
for (int i = 0; i < step; i++) {
goRight();
if (isTarget()) return true;
}
step *= 2;
}
}

最后分析复杂度的时候,对方给的N是target的值,而我一直用N=2^n的n在算,这是一个不好的。

最后复杂度是O(N)。可以这么想,最后从原点走到N的位置,最多走N步(因为初始位置0而且数组递增),而由于倍增,那么之前的相对应的步骤加起来也就是N(或者N-1)步。所以最后是O(N)。也可以推导出来。

上一篇:数据库系统Informix为例,介绍改善用户查询计划的方法。


下一篇:jquery-1.10.2.min.js之Multiple markers at this line