java - 以下函数的大符号是什么

Question

我无法找出这两个函数的最小上界。

我认为 ex1 有 O(log_3(n)) 而 ex5 应该有 O(n!)。但我对此并没有真正的信心，因为我还没有真正理解这个主题。

public int ex1 ( int n ) {
    int r = 0 ;
    for ( int i = 1 ; i < n ; i++) {
        r += n ;
        n = n / 3 ;
    }
    return r ;
}

public static int ex5 ( int n ) {
    int r = 1 ;
    for ( int i = 0 ; i < n ; i ++) {
            r += ex5 ( n - 1 ) ;
    }
    return r ;
}

Answer 1

ex5的输出值对应sequence A000522 at oeis.org , 随着 a(n) = Sum_{k=0..n} n!/k! 增加(或 n! 到第一个近似值)。由于这个函数的编码方式很糟糕，这等于函数的时间复杂度。

更好的算法如下:

public static int ex5 ( int n ) {
    return (n) ? 1 + n * ex5(n-1) : 1;
}

这显然是 O(n^2) O(n) ^{(抱歉，已经晚了，我需要 sleep !)}。

编辑: 正如其他人所说，ex1 的复杂度为 O(log_3(n))，或简单为 O(log(n))，因为 log_3(n) = log(n )/log(3), log(3) 在任何基数中都是常数。