代码之家 › 专栏 › 技术社区 › Snowman

伪码上的BigO界

performance pseudocode big-o algorithm

Snowman · 技术社区 · 16 年前

AllDistinct(a1 , . . . , an )
if (n = 1)
return True
for i := n down to 2
   begin
   if (LinearSearch(a1 , . . . , aiâ1 ; ai ) != 0)
     return False
   end
return True

对AllDistinct的运行时间进行大O限制。为了得到充分的信任,你必须证明工作或布里解释你的答案。

根据这个问题的解,这个问题的实际答案是O(n^2)。然而,既然BigO是最糟糕的运行时间,我能回答O(100000)并逃脱吗?因为从技术上讲这是正确的答案,所以他们不可能因此而扣分,对吧?虽然在这个算法中更有用的O(n^2)是显而易见的,但我问是因为在即将到来的考试中,我们可能会有一个更难的算法,如果我不能计算出“紧”界,我可以组成一些非常大的值,它仍然应该是正确的,对吧?

6 回复 | 直到 16 年前

sepp2k 16 年前

是的,如果函数在 O(n^2) ,它也在 O(n^1000) .

如果你决定走这条路,你可能应该选择 O(n^n) 或 O(Ackermann(n)) ,因为指数函数不在 O(1000英镑) .

另一个问题是你可能也会被要求证明边界。如果您不知道函数的运行时间,这将很难做到。” n^n 是真的很大,所以运行时间可能会比那要短”并不能证明。如果你能正确证明函数在 O(n^n) ,你可能至少会得到部分学分。

Ishtar 16 年前

(问大θ是个更难的问题。我会玩得很好:)

Martijn 16 年前

不。

可能都很聪明哈!我抓住你了!但这不是主意。(你也知道)

Fabio Filippi 16 年前

如果教授问你这个大问题,你可以回答任何你认为大的问题,但你必须按它说的去证明 For full credit, you must show work or brieï¬y explain your answer.

大人物不是没用的。对于问题,很容易得到上限(BigO)graeter;例如。

重要的是你明白它的意思 任何你可以把它写在试卷上,这是一个从学生到数字的函数。。祝你好运。

Jerry Coffin 16 年前

你可能得和教授谈谈,和他争论一下,这样的回答才能得到部分学分。根据他对理论和实践的重视程度,他可能会给你部分的评价,也可能不会给你任何的评价——但我很难想象一个教授,如果你不明确指出它是如何(半)正确的,而有些教授甚至可能不会。

Mike Dunlavey 16 年前

我是一个专业教授,会编考试题,而且这些题可能有漏洞。当你不得不抛出一个问题,因为它有一个错误,人们可以给一些琐碎的答案,这是令人难堪的。在这种情况下,错误是“ 大O型”。做试题很难,因为你不想在说太多的时候犯错,比如说一些不透风的律师声明,因为那样会让人更加困惑。

毕竟,这样做的原因是,希望你能学到一些有用的东西。如果你看到这样一个模棱两可的问题,如果你说“我想你是指大O型。”