Mob*_*obi 5 algorithm big-o analysis asymptotic-complexity
如果算法具有两个子算法,则当子算法A1对给定输入最佳情况时,对于子算法A2来说是最坏的情况.我怎样才能找到整体算法的复杂性？我只是说Ω(N)+ O(N)=？我知道算法是否按顺序执行顺序,所有复杂度都是O(N)+ O(N),并且嵌套顺序为O(N)*O(N).
在两种情况下,请按顺序和嵌套顺序告诉我
基本上Ω(N)+ O(N)=Ω(N).因为O(N)表示低(或至多相同)Ω(N)的量级.当它们相加时,可以省略较低的顺序.
如果您的算法包括一个需要 O(N) 时间的操作，另一个需要 O(N^2) 时间的操作，则总体复杂度为 O(N^2)。不存在 O(N^2 + N) 这样的事情。\xce\xa9() 也是如此。这回答了您关于“顺序执行顺序”的问题。
\n\n如果您的算法包含 N 个操作，每个操作都需要 O(N) 时间，则整体复杂度为 O(N^2)。\xce\xa9() 也是如此。您只需将多项式相乘，并取随着 N 的增加而增长最快的项。这回答了您关于“嵌套执行顺序”的问题。
\n