1

我在分析这种方法的大 O 复杂性时遇到问题。事实上，由于其令人困惑的性质，我也不确定该方法是如何工作的。现在，我所知道的是，将在数组中的“逐渐缩小的范围”中搜索给定的数字。有人可以解释以下代码并指导我如何分析其复杂性吗？

static int foo(int a[], int u, int l, int x) {
    while(l <= u) {
        int s = (u-l+1)/3, f = l+s, b = f+s;
        if(a[f] == x)
            return f;
        else if(a[b] == x)
            return b;
        else if(a[f] > x)
            u = f-1;
        else if(a[b] > x)
            l = b+1;
        else {
            l = b-1;
            u = f+1;
        }
    }
    return -1;
}
4

3 回答 3

1

似乎 l=low，u=upper，所以 ul 是范围。S 是范围的三分之一。该方法做了一些奇怪的事情，但在每次迭代中，范围缩小了三分之一。

如果范围缩小一半（如二进制搜索），那显然是 log n。但是这样，每次缩小三分之一..你怎么看？

于 2013-10-19T05:28:58.137 回答
0

看起来这段代码正在排序数组中搜索下索引和上索引之间的a值。它通过调整搜索区间的两端来实现这一点，其中包含一系列调整搜索中包含的下限或上限的子句。搜索的步长是范围的三分之一，“暂定的新边界”是和。根据解决方案是在新范围内还是现在，该算法将搜索范围缩小到旧区域的三分之一。xkus(u - l_ + 1)fb

为了更好地了解它的工作原理，我建议您打印出数字l以及u循环的每次迭代；然后增加大小x（例如，每次加倍）并重复。

当您绘制循环数与 x 的关系图时，您会很快看到，对于较大的 x，您是否会得到一条直线、抛物线或其他东西。您可以从中获得一些见解；运气好的话，这种关系很快就会变得清晰起来。

认识到大多数时候你会调整到大小的 1/3，所以迭代次数只会随着间隔的大小而缓慢上升——事实上，3 倍大的间隔只需要多一次迭代。这是O(log(n))过程的标志。

于 2013-10-19T05:38:25.750 回答
0

它是一个三元搜索，其复杂性还在O(lgn)。

于 2013-10-19T05:49:59.713 回答