java - 大O : is this the tightest upper bound for recursive algorithm?

Question

我的算法的时间复杂度是否低于 O(|2^{(2 + log3(n))} – 1|)？

有没有更优雅的写法？

int cantor(int low, int high) {
    int gap= (high - low) / 3;

    if (high < low)
        return 0;
    else if (high == low)
        return low;
    else
        return cantor(low, low + gap) + cantor(high - gap, high);
}

运行下面的 Java 程序会产生临界点，其中 n = 整数输入，o = 操作数，b = 上限(需要 >= o)

n    o    b 

0     1     1.0   <- critical point
1     3     3.0   <- critical point
2     3     5.194250610520971
3     7     7.0   <- critical point
4     7     8.592185156484856
5     7     10.04233615383682
6     7     11.388501221041942
7     7     12.65392426064557
8     7     13.85409969044663
9     15    15.0  <- critical point
10    15    16.099749365620383
11    15    17.159572545935887
12    15    18.184370312969712
13    15    19.178087273270823
14    15    20.143957171877723
15    15    21.08467230767364
16    15    22.0025040190721
17    15    22.899390537770895
18    15    23.777002442083877
19    15    24.636792344342172
20    15    25.480033236937405
21    15    26.30784852129114
22    15    27.1212358323658
23    15    27.92108616334829
24    15    28.708199380893266
25    15    29.48329693358293
26    15    30.2470323529008
27    31    31.0  <- critical point

这是Java代码:

public class recursionTreeTimeComplexity {

    static int calls = 0;

    static int cantor(int low, int high) {

        calls++;

        int gap = (high - low) / 3;

        if (high < low)
            return 0;
        else if (high == low)
            return low;
        else
            return cantor(low, low + gap) + cantor(high - gap, high);
    }

    public static void main(String[] args) {

        for (int i = 0; i < 1000; i++) {
            calls = 0;
            cantor(0, i);

            // |(2^log3(n)+2)|-1
            System.out.println(i + "\t" + calls + "\t" + Math.abs((Math.pow(2, ((Math.log(i) / Math.log(3)) + 2)) - 1)));    
        }
    }
}

Answer 1

说一个算法是 O(f(n)) 意味着时间大致与 f(n) 成正比(当 n 足够大时)。 [更新:这并不完全准确，因为实际时间可能会有很大差异并且不必单调递增。更准确地说，这意味着时间上有一个与 f(n) 大致成正比的上限。]

因此，在使用 O 表示法时添加常量是无关紧要的:O(f(n)+k) 与 O(f(n)) 相同，因为最终 f(n) 部分将占主导地位，而 k部分将变得可以忽略不计。此外，由于这是一个比例，乘以一个常数是无关紧要的； O(kf(n)) 与 O(f(n)) 相同，因为它们都说它基本上与 f(n) 成正比。这意味着原始表达式中的 +1 是无关紧要的，2+ 也是如此，因为 2^(2+x) = 4* 2^x，这意味着您只是乘以一个常数。所以你的原始表达式可以简化为 O(2^(log₃n))。这似乎是正确的；正如我确定您注意到的那样，如果 T(n) 是算法的运行时间，那么基本上 T(n) = 2T(n/3) [非常粗略，但这对于这个目的来说已经足够了]，这意味着如果我们假设 T(1)=1，那么 T(3)=2，T(9)=4，T(27)=8，等等。

我们可以进一步简化。 log₃n = log₂n/log₂3;因此 2^(log₃n) = 2^(log₂n/log₂3) = (2^log₂ n)^(1/log₂3) = n^(1/log₂3) = n^(log₃2).所以算法的时间可以表示为O(n^(log₃2))，或者大约O(n^0.6309)。