algorithm - 多个语句的大 O 表示法

Question

假设有多个具有某些大 o 符号的函数，任何 O(N)、O(N^2) 等。如果你有一个代码片段，例如。

 f1(x);
 f2(x);
 f3(x);

所有的大 O 符号是加在一起还是相乘？关于为什么任何一个都是正确的 - 加法或乘法的任何解释？

Answer 1

两者都不。你会取最大值。

调用更大的代码g...如果例如 O( f2) >= O( f1) 且 O( f2) >= O( f3)，则复杂度g为 <= 3 * O( f2) = O( f2)。

Answer 2

假设它们不修改x，则将 O 符号相加，因为完成这三个符号所花费的时间是单独完成每个符号所花费的时间之和。