1

このメソッドの Big 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 は範囲の 3 分の 1 です。このメソッドは奇妙なことを行いますが、反復ごとに範囲が 3 分の 1 ずつ縮小します。

範囲が (二分探索のように) 半分に縮小された場合、それは明らかに log n になります。しかし、この方法では、毎回 3 分の 1 ずつ縮小します.. どう思いますか?

于 2013-10-19T05:28:58.137 に答える