O（kn）是線性複雜度還是二次複雜度？或者它依賴於k？

如果k關閉到n/2但不超過n/2，該怎麼辦？我是否認爲它仍然是線性複雜性？或二次複雜度O（n^2）？

將O（kn）視爲二次型複雜度是否有限制k是多大？

2012-10-31 Michael

如果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）。

2012-10-31 15:30:55

如果k是m的函數並且是O（m），並且給定m << n，我可以說O（kn）是線性的嗎？ – Michael

@邁克爾：不一定。例如，如果'm'是'log log n'那麼'n * log log n'不是O（n）。但對於所有實際用途而言，它足夠接近線性。我建議你看看大O符號的定義，如果你明白那就可以分析你的實際功能。 –

謝謝你的很好的解釋 – Michael

假設k和n是獨立變量，說O（kn）是線性的是一個恰當的說法。

2012-10-31 15:31:16

回答