是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）？

回答

相关问题