二次算法的時間複雜度

對於我的編程和算法設計考試，我必須熟悉時間複雜性和Big-Oh符號。我理解它的大部分內容，但後來我碰到這個問題，我的解決方案似乎相當簡單;但我不明白哪些步驟是必要的。有人可以澄清步驟了嗎？二次算法的時間複雜度

練習：

的二次算法的處理時間T（N）= CN^2花費T（N）秒用於處理N個數據項。假設N = 100且T（N）= 1ms，將花費多少時間來處理n = 3000個數據項目？

鑑於溶液：

常數因子c = T（N）/（N^2），因此T（N）= T（N）*（N^2）/（N^2）= n^2/10000和 T（3000）= 900ms

我完全和'n'和'N'混淆。兩者都是數據項的數量，但它們有所不同。 –

N和n看起來是一樣的。我認爲N用來表示一個特定的例子。 –

真的嗎？「假設N = 100，需要花費多少時間來處理n = 3000個數據項」 –

這是一個非常簡單的數學題：

如果T(n) = cn²和T(100) = 1ms然後

T(100) = c * 100² 
     = c * 10,000 
     = 1ms

因此求解c給出：

c = (1/10,000)ms

這可以被用來計算T(3000)：

T(3000) = (1/10,000)ms * 3,000² 
     = (1/10,000)ms * 9,000,000 
     = (9,000,000/10,000)ms 
     = 900ms

2014-01-25 12:40:37 Iridium

哦哇，我只是看錯了方式......哈哈，非常感謝！ *臉紅* – user3235058

它是直截了當的。您有N = 100，T(N) = 1。所以c = T(N)/N^2 = 1/10000。

然後你做T(3000) = 1/10000 * (3000^2) = 900。

2014-01-25 12:40:01

這與Big-Oh notation，甚至計算機科學沒有任何關係。所有你需要的是基礎代數。考慮到T（n）= cn^2對於某些c，T（100）= 0.001，T（3000）是多少？

0.001 = T(100) = c (100*100) = 10000c 
    c = 10^-7 

    T(3000) = c n^2 = 10^-7 * 3000 * 3000 = 0.9

2014-01-25 12:40:27 meriton

回答