对于某个问题，如果我有一个 O(f1(m,n)) 算法和一个 O(f2(m,n)) 算法，我可以有一个 O(min(f1(m,n),f2) 算法吗？ (m,n))) 算法？

Question

实际上，我有这个问题是因为 clrs 14.3.4 https://walkccc.me/CLRS/Chap14/14.3/ 我知道如何证明遍历的 O(N) 和删除每个的 O(klogN)时间。那么如何证明存在 O(min(N,klogN)) 就成了一个问题。 （我在如何证明区间树查询的时间复杂度中问过）

断言这是正确的，任何具有 O(f1(m,n)) 和 O(f2(m,n)) 解决方案的算法都可以具有 O(min(f1(m,n),f2(m,n) ))) 解决方案（执行前 m,n 未知）。

Answer 1

是的。 如果你有一个 O(f1(m,n)) 和一个 O(f2(m,n)) 解决方案，你可以 以伪并行（时间切片）执行每个解决方案，并在其中一个找到解决方案时停止。

这样你就得到了 O(min(f1(m,n),f2(m,n))) 算法。

这比执行首先单独找到解决方案的算法慢 2 倍，但根据 O 符号，这没有区别（因为 2 只是一个常数因子）。