0

我一直在做一些问题，但没有提供答案，所以我想知道我的答案是否正确

a) 假设 a[i....j] 是一个具有 n 个元素的整数数组并且 x 是一个整数

int front, back;

while(i <= j) {

    front = (i + j) / 3; 
    back = 2 * (i + j) / 3;

    if(a[front] == x)
        return front;
    if (a[back] ==x)
        return back;

    if(x < a[front])
        j = front - 1;
    else if(x > a[back])
        i = back+1;
    else {
        j = back-1;
        i = front + 1;
    }
}

我的答案是 O(1)，但我觉得我错了。

二）

public static void whatIs(int n) {
    if (n > 0)
        System.out.print(n+" "+whatIs(n/2)+" "+whatIs(n/2));
}

ans：我不确定是 log4n 还是 logn，因为递归发生了两次。

4

3 回答 3

4

一）是的。 O(1)是错的。您将循环多次，这取决于i, j, x... 和数组的内容。算出你在最好和最坏情况下绕圈的次数。

B)log(4*n)使用log(a*b) -> log(a) + log(b)（基础高中数学）进行化简，然后应用大 O 的定义。

但这也不是正确的答案。再一次，您应该回到第一原则并计算为给定参数值调用该方法的次数n。并进行归纳证明。

于 2012-04-10T06:49:59.840 回答
0

两个答案都不正确。

在每次迭代的第一个示例中，您要么找到数字，要么将间隔的长度缩小 1/3。即，如果长度曾经是 n，则将其设为 (2/3)*n。最坏的情况是你在最后一次迭代中找到 x - 当间隔的长度为 1 时。所以就像二进制搜索一样，复杂性是通过对数计算的：复杂性是 O(log 3/2 (n)) 而这实际上只是 O(log(n))

在给定数字 n 的第二个示例中，您执行 n/2 所需操作数的两倍。从 n = 0 和 n = 1 开始，使用归纳法证明复杂度实际上是 O(n)。

希望这可以帮助。

于 2012-04-10T06:49:28.877 回答
0

A）这个算法看起来类似于黄金分割搜索。在分析复杂性时，有时更容易想象如果我们扩展数据结构而不是收缩它会发生什么。可以这样想：每个循环从搜索间隔中删除三分之一。这意味着，如果我们确切地知道某个长度需要多长时间，如果我们被允许再次循环，我们可以增加 50% - 指数增长。因此，搜索算法必须具有复杂度 O(log n )。

B) 每次我们添加一个“层”函数调用时，我们都需要将它们的数量加倍（因为函数总是调用自己两次）。换句话说，给定一定的长度和时间消耗，将n加倍也需要在最后一层中调用两倍的函数。算法是 O( n )。

于 2012-04-10T07:10:07.167 回答