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

Question

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

Answer 1

冒泡排序是大 O k^2 复杂度，最坏情况和平均值

所以我们有 n 个大小为 k 的操作，这意味着 k^2 = n

所以我们将 k 加倍，我们有 (2k)^2 = X 或 4k^2 = X 其中 X =# of operations for 2k size

代入 n=k^2 的事实，你有 4n=X

有你的答案:)