BigO 绑定在一些伪代码上
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(n^100000) 并侥幸逃脱吗？他们不可能因此扣分，因为从技术上讲这是正确的答案，对吗？虽然在这个算法中更有用的 O(n^2) 是显而易见的，但我问是因为我们在即将到来的考试中可能会有一个更困难的算法，并且万一我无法弄清楚“紧”界，我可以编一些非常大的算法值，它应该仍然是正确的，对吗？
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
Give a big-O bound on the running time of AllDistinct. For full credit, you must show
work or briefly explain your answer.
So the actual answer for this according to the solution for this problem is O(n^2). However, since BigO is the worst case running time, could I have answered O(n^100000) and gotten away with it? Theres no way they can take points off for that since its technically the correct answer right? Although the more useful O(n^2) is obvious in this algorithm, I ask because we might have a more difficult algorithm on the upcoming exam, and incase I cant figure out the 'tight' bound, I could make up some extremely large value and it should still be correct, right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
是的，如果一个函数的复杂度为
O(n^2)，那么它的复杂度也为O(n^1000)。当然，您是否会以这种方式回答获得全部（或任何）学分取决于给您的考试评分的人，所以我不能告诉您这一点（但可能不会）。但是，是的，这在技术上是正确的。
如果您确实决定这样做，您可能应该选择类似 O(n^n) 或 O(Ackermann(n)) 的东西，因为例如指数函数不在
O(n^1000)范围内。另一个问题是，您可能还会被要求证明界限。如果您实际上不知道函数的运行时间，这将很难做到。 “
n^n确实很大，因此运行时间可能会比这个少”并不是一个证明。不过，从好的方面来说，如果您能够正确证明该函数的复杂度为O(n^n)，那么您可能至少会获得部分功劳。Yes, if a function is in
O(n^2), it is also inO(n^1000).Whether you'll get full (or any) credit for answering this way depends on the person grading your exam of course, so I can't tell you that (probably not though). But yes, it is technically correct.
If you do decide to go this way though, you should probably chose something like
O(n^n)orO(Ackermann(n)), since for example exponential functions are not inO(n^1000).Another problem is that you will probably be asked to proof the bound as well. This will be hard to do if you don't actually know the running time of the function. "
n^nis really large, so the running time will probably be less than that" is not a proof. Though on the upside if you manage to correctly proof that the function is inO(n^n), you'll probably get at least partial credit.这对这个问题来说是一个微不足道的答案。虽然它是正确的，但它没有告诉你任何信息，因此毫无价值。这不是关于对或错，而是关于坏和好。您的答案越好，您获得的分数就越多。这个问题并不是说你会因可怕的坏界而受到赞扬。不好的答案会给不好的分数吗？
（询问 Big Theta 将是一个更难的问题。我会表现得很好:)
That would be a trivial answer to the question. Although correct, it tells you nothing and is thus worthless. It's not about right or wrong, it's about bad and good. The better your answer, the more points you'll get for it. The question does not say you'll get credit for a terrible bad bound. Bad answers give bad marks?
(Asking for Big Theta would be a harder question. I would play nice :)
不。
这可能很聪明，哈哈！我接到你了！但事实并非如此。 （你知道的）
No.
It might be all clever and HA! I got you! but that's not the idea. (and you know that)
如果教授向您询问 BigO，您可以回答您认为的任何 BigO，但您必须证明它，正如它所说的
要获得满分，您必须展示工作或简要解释您的答案。BigO 并非无用。对于问题，很容易获得更大的上界（BigO）；例如
排序问题：你有简单的冒泡排序，你可以证明它是 n^2 （对吗？），所以排序问题的上限是 n^2 （因为当时存在解决它的算法，但如果你继续通过数学，您会发现问题的下限为 log(n!) ）。所以 n^2 是一个很好的答案，直到你证明它是 log(n!)。有很多问题我们只知道BigO而不知道下界，所以它并不是没有用。
如果你可以说一个程序停止了，你总是可以用一些数学来计算 BigO，但并不总是那么容易（甚至存在摊销复杂性），但它比问题 lowerBound 更简单。所以BigO在算法上并不是那么重要，但也不是没有用。
重要的是你理解它的含义；那么如果你能得到该程序的任何 BigO，你就可以把它写在试卷上，这是从学生到数字的函数..祝你好运。
If the professor ask you for BigO of it you can answer whatever BigO you think but you must prove it as it say
For full credit, you must show work or briefly explain your answer.BigO is not useless. For problems it's easy to get Upper Bound (BigO) graeter; e.g.
Sorting problem: you have the simple bubble sort and you can proof that is n^2 (right?), so upper bound of Sorting problem is n^2 (because exists and algorithm that solve it in that time, but if you go on with maths, you see that the problem has a lower bound of log(n!) ). So n^2 was a good answer until you proof it's log(n!). There are many problems that we know just BigO but not the lower bound, so it's not useless.
If you can say that a program halts you can always compute is BigO with some math, but is not always easy (exists even ammortized complexity) but it's simpler than problems lowerBound. So BigO is not so important in algorithm, but it's not useless.
The important thing is that you understand what it means; then if you can get any BigO of that program you can write it on that exam paper that is a function from Student to number.. and good luck.
据猜测，你可能需要和教授交谈，并与他争论一下，才能获得这样的答案的部分学分。根据他对理论与实践的重视程度，他可能会给你部分学分，或者他可能不给你学分——但我很难想象一个教授会在没有你明确指出它是如何（半）的情况下给予任何学分正确，有些人甚至可能不正确。
At a guess, you'd probably have to talk to the professor, and argue with him a bit to even get partial credit for an answer like that. Depending on how much he values theory vs. practicality, he might give you partial credit, or he might give no credit -- but I can hardly imagine a professor who'd give any credit without your explicitly pointing out how it's (semi-)correct, and some might not even then.
我是一名教授。教授们编造的考试题可能存在错误。当你不得不抛出一个问题，因为它有一个错误，而人们只能给出微不足道的答案时，这是很尴尬的。在这种情况下，错误是“a big-O 界限”。制作考试题很棘手，因为你不想因为说太多而犯错，比如某种严密的律师声明，因为这会让人们更加困惑。
毕竟，这样做的原因是希望您能学到一些有用的东西。如果你看到这样一个模棱两可的问题，如果你说“我认为你的意思是一个好的大O界限”，教授会很感激的。
I was a prof. Profs make up exam questions, and those can have bugs. It's embarrasing when you have to throw out a question because it's got a bug and people can give trivial answers. In this case the bug is "a big-O bound". Making exam questions is tricky, because you don't want to err on the side of saying too much, like some kind of airtight lawyer statement, because that will confuse people even more.
After all, the reason for doing this is, hopefully, you'll learn something useful. If you see an ambiguous question like this, the prof will appreciate it if you say something like "I assume you mean a good big-O bound."