c - 冒泡排序 - 如果需要 n 次操作来对大小为 k 的列表进行排序，那么大约需要多少次操作来对大小为 2k 的列表进行排序？

Question

就目前情况而言，这个问题不太适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、民意调查或扩展讨论。如果您觉得这个问题可以改进并可能重新开放， visit the help center以获得指导。

已关闭 10 年前。

这是我正在学习的类(class)中的一个可选问题，他们提供了答案，4n。但现在无论我怎么想，我都无法弄清楚他们是如何走到这一步的。我还是个新手，刚刚学习大 O 表示法，所以我确信我错过了一些简单的东西，但这对我来说没有意义。我的想法是冒泡排序需要 n * k 次操作，所以如果你把 k 变成 2k 我有 n * 2k 。我相信在最坏的情况下 k = n - 1 所以它实际上是 n * 2n 又名 3n。我可能做错了，但这就是我来这里寻求帮助的原因。我的类(class)并没有真正(或者我不觉得)涵盖这样的问题，所以我只是不确定如何解决它。谢谢!

Answer 1

冒泡排序的复杂度是 Big O k^2，无论是最坏情况还是平均情况

所以我们对大小 k 有 n 次操作，这意味着 k^2 = n

所以我们将 k 加倍，得到 (2k)^2 = X 或 4k^2 = X，其中 X = 2k 大小的操作数

代入 n=k^2，则有 4n=X

这就是你的答案:)