这个函数的大O符号是什么？

我知道大O符号是衡量一个函数效率的一个度量，但我真的不知道如何计算它。这个函数的大O符号是什么？

def method(n) 
    sum = 0 
    for i in range(85) 
     sum += i * n 
    return sum

答案是否是O（f（85））？

来源

2013-12-11 kiasy

这里的运行时间似乎是不变的（即不变的'n'）... –

你有4个“动作”功能，来计算其大O上，我们需要计算大O字的每一个动作，然后选择最高：

总和= 0 - 固定的时间，测量O（1）
我在范围（85） - 恒定时间，85次迭代，O（1 *复杂度为＃3）
sum + = i * n - 我们可以说恒定时间，但乘法实际上取决于位长度我和n，所以我们可以说O（1）或者O（max（lenI，lenN））
return sum - constant time，measured O（1）

因此，只要lenI和lenN是常数（通常为32或64位），max（lenI，lenN）就是可能的最大大O是＃2，即1 * O（＃3） - > 32/64，所以你的函数的总复杂度是O（1 * 1）= O（1）

如果我们有大的数学，即N的位长度可以非常长，那么我们可以说O（位长N）

注：位长N实际上是LOG2（N）

来源

2013-12-11 20:19:25

...更新了我的答案，O（log2 n）等于O（log n）。 – pepr

@pepr在数学世界中最好提到日志库，因为只是日志通常意味着log10，而在计算机世界中日志通常意味着log2。所以我更喜欢在这里指出基地（当然，您可以通过const从log2转换为log10，然后只需写入无日志的日志） –

我知道你知道。 :)而且任何常量都不会改变O（）。 – pepr

的此功能的复杂性是在RAM模型发生在固定时间内基本的数学函数O（1）

。在此函数中的主导术语是

for i in range(85):

因为85是一个恒定的复杂度为O（1）表示

来源

2013-12-11 20:12:52 robbmj

你能解释为什么吗？ – kiasy

我用解释 – robbmj

在理论上，复杂度为O（log n）的。随着n增长，读取数字并执行乘法需要更长的时间。

但是，在实践中，n的值受到限制（有一个最大值），因此可以在O（1）时间内读取并执行操作。由于我们重复O（1）操作一定的时间，所以复杂度仍然是O（1）。请注意，O（1）表示常量时间 - O（85）并不意味着任何不同。如果在一个序列中执行多个常量时间操作，则除非序列的长度取决于输入的大小，否则结果仍为O（1）。执行O（1）操作1000次仍然是O(1)，但这样做n次是O(n)。

如果你想真的玩起来安全，就说O(∞)，那绝对是一个正确的答案。然而，CS教师在实践中往往不会真正欣赏它。

来源

2013-12-11 20:19:21 kviiri

当谈到复杂性时，总是应该说什么操作应该被视为恒定时间（最初的协议）。这里可以考虑整数乘法或者是不变的。无论如何，这个例子的时间复杂度比O（n）好。但这是老师对学生的诡计 - 有点儿。 :)

来源

2013-12-11 20:57:37 pepr

这个函数的大O符号是什么？

回答

相关问题