最坏的情况下运行时间（大O）

我有这个问题，我不知道如何解决它，因为我不明白它。 :(最坏的情况下运行时间（大O）

的问题是：

程序A和B进行了分析，发现具有最坏的情况下的运行时间不大于150 Ñ日志Ñ和Ñ ，回答下列问题：

i）哪个程序对大型运行时间有更好的保证值n（n> 10000）？

II）的程序具有的ñ（ñ < 100小值）上运行的时间更好的保障？

任何人都可以帮我解释一下吗？

来源

2009-11-17 Youki

你还没有告诉我们任何关于n2的价值？从（i）到（ii）是不变的吗？ – tster 2009-11-17 16:47:11

我猜这是n^2。 – 2009-11-17 16:48:19

是的，它意味着n^2（sequare） – Youki 2009-11-17 18:45:39

给你两个公式和n两个不同的值来插入它们。然后询问每种情况下哪个公式具有较大的值。

我建议将n这两个值插入公式中，并找出每种情况下哪个更大。

来源

2009-11-17 16:48:03

你有话要说“把n的两个值插入公式中，并找出每种情况下哪个更大”。现在，当我解决它时，我发现furmula（150n log n）在两种情况下具有较大值，看起来如下：在第一部分[i]如果选择数字11000> 10000，已经在两个农场里计算出来了，我发现（150n log n）有更大的价值。在第二部分[ii]我选择了数字99，它<100，我发现（150n log n）也有更大的值。我有正确的理解吗？很抱歉，但我们的老师从来不解释:( – Youki 2009-11-17 18:55:09

150 * 11000 *日志（11000）远低于11000 * 11000较小，实际上，请尝试重新计算了。 – 2009-11-17 19:33:21

OBSS，H已经丢失的财产以后。 UR权。我再次尝试，我发现furmula（N^2）具有较大的值。 – Youki 2009-11-17 20:02:30

最差情况下的运行时间意味着给定输入长度为n的程序将运行的绝对时间最长。所以你给出的两个公式是他们最糟糕的情况下运行时间。在数学上，两个公式在n的不同尺寸下表现不同。尝试n的大小，看看他们如何回应。这将帮助你理解并找到你的答案。

来源

2009-11-17 16:50:26 Poindexter

我已经在做你在说什么了：当我解决它时我发现furmula（150n log n）具有较大的值这两种情况，看起来：在第一部分[i]如果我选择数字11000> 10000，我已经在两个farmulas中计算出它，并且我发现（150n log n）具有较大的值 In第二部分[i i]我选择了小于99的数字99，并且我发现（150n log n）也有更大的值 – Youki 2009-11-17 19:01:31

请看WolframAlpha。最坏的情况相同的点大约在1042.这应该回答你的问题。

来源

2009-11-17 16:54:58

由于这是算法作业，因此log可能基于2而不是自然对数。 – bcat 2009-11-17 17:00:14

我已经看到了图表。你是否想说（150n log n）有很大的价值？ – Youki 2009-11-17 18:58:14

奇怪！对于0 <= n <1402：150 * n * log（n）> n^2;对于1402 <= n：150 * n * log（n） 2009-11-17 20:23:26

-1

如果实际问题是O（n^2），那么ii是一个技巧性问题。

在Big-O符号中，可以删除常量，因此O（10000n^2）与O（n^2）相同。如果你还没有从问题中删除O（），那么只需填写方程，这应该不难解决。

来源

2009-11-17 16:55:17

但它并不想要大O符号.. 我已经说了：（ – Youki 2009-11-17 19:04:04