关注的重要标志是什么？

Question

我无法弄清楚这两者的最小障碍

我想到第一个的log3(n)和第二个的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 的输出值对应于oeis.org 上的序列 A000522，其增加为 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) ^{（抱歉，很晚了，我需要睡觉！）}。

编辑：正如其他人所说， ex1 的复杂度是 O(log_3(n))，或者只是 O(log(n))，因为 log_3(n) = log(n)/log(3)，并且 log( 3) 是任意底数的常数。