algorithm - 如何添加大 O 和大欧米茄

Question

如果一个算法有两个子算法，当子算法 A1 对给定输入最好的情况下，它是子算法 A2 的最坏情况。我怎样才能找到整体算法的复杂性？我的意思是Ω（N）+ O（N）=？我知道算法是否按顺序执行顺序，总体复杂度为 O(N)+ O(N)，嵌套顺序为 O(N)* O(N)。

请告诉我在这两种情况下，按顺序和嵌套顺序

Answer 1

本质上 Ω(N) + O(N)= Ω(N)。因为 O(N) 表示 Ω(N) 的更低（或最多相同）阶。当它们相加时，可以省略较低的顺序。

Answer 2

如果您的算法包括一个需要（例如）O(N) 时间的操作和另一个需要 O(N^2) 时间的操作，那么总体复杂度是 O(N^2)。没有像 O(N^2 + N) 这样的东西。Ω() 也是如此。这回答了您关于“顺序执行顺序”的问题。

如果您的算法包括 N 个操作，每个操作都需要 O(N) 时间，那么总体复杂度为 O(N^2)。Ω() 也是如此。您只需将多项式相乘，并采用随着 N 增加而增长最快的术语。这回答了您关于“嵌套执行顺序”的问题。