algorithm - 递归置换函数的复杂度

Question

我有一个递归函数，其中的子函数/操作具有以下复杂性：

1. （n-1）！
2. (n-1)
3. O(n-1)
4. O(log((n-1)!)) + O(n)

我想知道整个函数的渐近复杂度。我该怎么做呢？

Answer 1

我认为这可能会对您有所帮助：

f1(x) = O(g1)
f2(x) = O(g2)
=> f1+f2 = O(max(g1, g2))

所以你可以说函数求和的复杂度等于计算顺序最大的那个。

Answer 2

简短的回答是您使用重复关系，请参阅例如 http://en.wikipedia.org/wiki/Recurrence_relation

对于案例 2 和 3，您最终会得到 O(n^2)，对于案​​例 1 和 4，如果不进行实际数学计算，我不确定。