algorithm - O(kn) 是线性复杂度还是二次复杂度？还是取决于k？

Question

如果 n 很大，而 k 很小，我可以说 O(kn) 是线性复杂度吗？

如果 k 接近于 n/2 但不大于 n/2 会怎样？我是否仍然认为它是线性复杂性？还是二次复杂度 O(n^2)？

将 O(kn) 视为二次复杂度，k 的大小是否有限制？

Answer 1

如果k是一个常数，那么任何O(kn)函数都是O(n)，即线性

如果k是的函数n并且是 O(n)，那么任何 O(kn) 函数都是 O(n^2)。n/2 是 O(n)。此外，(n^2)/2不是O(n)，因此如果接近then不是O(n)。kn/2kn

如果k不是 O(n)，则kn不是 O(n^2)。

Answer 2

假设 k 和 n 是自变量，说 O(kn) 是线性的是正确的陈述。