time-complexity - 两种算法一起运行的时间复杂度？

Question

假设T₁(n)和T₂(n)是P₁和P_{2 程序，和}

T₁(n) ∈ O(f(n))

T₂(n) ∈ O(g(n))

当P₁沿边P<运行时，T₁(n)+T₂(n)的数量是多少子>2 ?

答案是 O(max{f(n), g(n)}) 但为什么呢？

Answer 1

当我们考虑 Big-O 表示法时，我们通常会考虑当输入 n 的大小变得非常大时算法会做什么。很多时候，我们可以依靠某种数学直觉。考虑两个函数，一个是 O(n^2)，一个是 O(n)。随着 n 变得非常大，两种算法都会无限增加。不同之处在于，O(n^2) 算法的增长速度比 O(n) 快得多。实际上，如果将算法组合成 O(n^2+n) 的东西，n 本身的因数非常小，以至于可以忽略，算法还在O(n^2)类中。

这就是为什么当您将两个算法加在一起时，合并的运行时间在 O(max{f(n), g(n)}) 中。总有一个“支配”运行时，使另一个的影响可以忽略不计。