Mic*_*ael 3 algorithm complexity-theory time-complexity
如果n很大,k非常小,我可以说O(kn)是线性复杂度吗？
如果k接近n/2但不超过n/2怎么办？我认为它仍然是线性复杂性吗？或二次复杂度O(n ^ 2)？
考虑O(kn)是二次复杂度,k有多大是有限制的吗？
Ste*_*sop 15
如果k是常数,那么任何O(kn)函数都是O(n),即线性
如果k是和的函数n是O(n),那么任何O(kn)函数都是O(n ^ 2).n/2是O(n).此外,(n^2)/2是不为O(n),并且因此,如果k是接近n/2则kn是不为O(n).
如果k不是O(n),则kn不是O(n ^ 2).