计算包含两个连续函数的函数的复杂度

Question

如果我们有一个包含两个顺序函数的算法

x

，第一个的复杂度是

f(n)

，第二个是

g(n)

，那么算法

x

的复杂度是多少？

例如：

x(x){
  f(n);
  g(n)
}

是

Max(f(n),g(n))

，

g(n)+f(n)

还是别的什么？

Answer 1

算法 x 的复杂度，包括复杂度为 f(n) 和 g(n) 的两个顺序函数，可以通过考虑最坏情况来确定。

在这种情况下，算法 x 的复杂度将是两个函数的复杂度之和。因此，算法x的复杂度可以表示为f(n) + g(n)。

需要注意的是，这假设函数 f(n) 和 g(n) 彼此独立，并且没有任何可能影响其各自复杂性的交互或依赖关系。