如果一个算法有两个子算法，当子算法 A1 对给定输入最好的情况下，它是子算法 A2 的最坏情况。我怎样才能找到整体算法的复杂性？我的意思是Ω（N）+ O（N）=？我知道算法是否按顺序执行顺序，总体复杂度为 O(N)+ O(N)，嵌套顺序为 O(N)* O(N)。
请告诉我在这两种情况下，按顺序和嵌套顺序
问问题
2009 次
2 回答
5
本质上 Ω(N) + O(N)= Ω(N)。因为 O(N) 表示 Ω(N) 的更低（或最多相同）阶。当它们相加时，可以省略较低的顺序。
于 2012-09-23T17:09:01.197 回答
4
如果您的算法包括一个需要（例如）O(N) 时间的操作和另一个需要 O(N^2) 时间的操作，那么总体复杂度是 O(N^2)。没有像 O(N^2 + N) 这样的东西。Ω() 也是如此。这回答了您关于“顺序执行顺序”的问题。
如果您的算法包括 N 个操作，每个操作都需要 O(N) 时间，那么总体复杂度为 O(N^2)。Ω() 也是如此。您只需将多项式相乘，并采用随着 N 增加而增长最快的术语。这回答了您关于“嵌套执行顺序”的问题。
于 2012-09-23T17:06:09.530 回答