两次通过数组为O（n）或O（2N）

我是在采访蛋糕练的一些问题，以及问题2给出的解决方案采用两个独立的回路（未嵌套）和解决方案供应商声称，他/她在O（n）时间解决了它。根据我的理解，这将是O（2n）次。我的想法是错误的，还是解决方案提供商犯了错误？从采访蛋糕两次通过数组为O（n）或O（2N）

摘录：

2016-03-08 Hossam

O（n）== O（2n）== O（kn）。常量不重要，只有比例因子。 – azurefrog

O（2n）摊销到O（n），因为与“n”相比，因素“2”具有不成比例的小影响（在最坏的情况下） –

完美，谢谢！ – Hossam

大O符号为您提供关于如何做你的算法执行时间取决于输入数据的提示。当你看到那个时间复杂度为O（n）的你明白，有输入和执行时间之间的线性依赖。常量没有提及。

根据定义＆奥米克;（G（N））是每个的所述下面的语句保持组函数：存在这样的正的常数Ç和Ñ该0 ≤F（N）≤CG（n）的适用于所有ñ≥ñ。你看定义是使用任意常数Ç，如果你的克（N）本身具有恒定的，不会有任何区别。

最终，我们有：O（CG（n））的 = O（G（N））。在特定情况下O（CN） = O（2N） = 为O（n）。它们都代表相同的一组功能。

2016-03-08 20:44:48

那么，如果面试官在采访中要求开发一个在O（n）时间运行的算法，并且我在O（2n）时间内写一个算法，那么这不应该是一个主要问题？ – Hossam

@Hossam，它只是**冗余**说* O（2n）*，因为它与* O（n）*相同。我不认为这会影响你的采访结果:)。 –

大O符号是最有用的，看看如何代码规模。也就是说，如果我将数组的大小加倍，代码需要多长时间才能运行？如果您的代码是O(n)，则需要两倍的时间，而如果是O(n^2)，则需要4倍的时间，以此类推。在这种情况下，无论您是否通过循环两次，将数组的大小加倍会比以前长两倍（每个循环的长度是两倍）。

2016-03-08 20:35:14

回答