Steven Skiena的《算法设计手册》第1章练习中有这样一个问题:
假设P是一个问题,它的最坏时间复杂度为O(n^2),同时也有一个最坏时间复杂度为Ω(n log n)。A是一个解决P的算法。以下哪些陈述符合关于P复杂度的信息?
- A的最坏时间复杂度为O(n^2)。 - A的最坏时间复杂度为O(n^3/2)。 - A的最坏时间复杂度为O(n)。 - A的最坏时间复杂度为⍬(n^2)。 - A的最坏时间复杂度为⍬(n^3)。
一个算法如何能拥有两种最坏时间复杂度?作者是不是想说,对于某些值(例如300),编写用于解决P的算法的上限为O(n^2),而对于另一个值(例如3000),相同的算法的最坏情况是Ω(n log n)?
假设P是一个问题,它的最坏时间复杂度为O(n^2),同时也有一个最坏时间复杂度为Ω(n log n)。A是一个解决P的算法。以下哪些陈述符合关于P复杂度的信息?
- A的最坏时间复杂度为O(n^2)。 - A的最坏时间复杂度为O(n^3/2)。 - A的最坏时间复杂度为O(n)。 - A的最坏时间复杂度为⍬(n^2)。 - A的最坏时间复杂度为⍬(n^3)。
一个算法如何能拥有两种最坏时间复杂度?作者是不是想说,对于某些值(例如300),编写用于解决P的算法的上限为O(n^2),而对于另一个值(例如3000),相同的算法的最坏情况是Ω(n log n)?