是O（LogN）== O（3LogN）？

我剛開始了一個關於漸近分析的課程，在我的任務之一中，我應該在不改變複雜性的情況下爲功能添加功能。複雜度是log（N）。作業指南特意要求我用「常量」來改變運行時間。會讓它變成3Log（N）常數？是O（LogN）== O（3LogN）？

2012-04-27 devjeetroy

您忘記了'O（log N）'的確切定義嗎？回到定義來理解答案是微不足道的*是* – 2012-04-27 05:07:47

你能說明你是如何得到'3log（n）'的？ – noMAD 2012-04-27 05:08:01

我相信增加一些東西，如（常數+ log（N））將被視爲增加一個常數因子，而3LogN將會相乘。雖然我根據定義知道O（3LogN）= o（LogN），但我覺得我的導師意味着添加形式。事情是，我不想在我的任務中抓住任何機會，所以我想與更有知識的人一起澄清。 – devjeetroy 2012-04-27 05:16:49

是的，更具體地說，這將改變乘法常數。你也可以用一個像log(N)+5這樣的加法常數來改變它。

來源

2012-04-27 05:08:27 trutheality

是的，這個東西正在改變算法的多倍，像'3'這樣的事情是非常不可能的，除非你做了像3次嵌套循環那樣的事情，這再次可能不是最佳的解決方案。 – noMAD 2012-04-27 05:10:37

原始功能涉及向二叉搜索樹添加元素。爲了完成我的任務，我不得不修改代碼，以便遍歷樹不是一次，而是兩次。那是2LogN？ – devjeetroy 2012-04-27 05:18:40

@noMAD需要在數據結構上傳遞一個常數，或者在迭代中添加一個固定數量的操作並不罕見。 – trutheality 2012-04-27 05:20:53

是O（LogN）== O（3LogN）？

回答

相關問題