最壞的情況下運行時間（大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