如何添加Big O和Big omega

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增加而增长最快的项。这回答了你关于“嵌套执行顺序”的问题。