大O和時間複雜度

假設已知算法是O（N ）並且解決大小爲M的問題需要5分鐘。關於解決4M尺寸問題需要多長時間？大O和時間複雜度

它是那樣簡單......

M = 5分鐘 4M = 20分鐘

？

來源

2014-04-15 user3534193

不能計算實時功耗。大O只是一個近似值，但你可以估計，在4M的大小下，時間是5 *（4 * 4）= 80min – kaitian521

這裏的關鍵是所需時間隨着物品數量的平方增加。因此，兩倍的項目需要四倍的時間（即2^2）。四倍的項目將需要16倍的時間（4^2）。 10倍的項目將需要100倍的時間（10^2）等。 –

既然Big O只是一個近似值，你不能計算實時，但是你可以有一些估計。在你的情況下，將

1 M ~ 5 min 
4 M ~ 5 *(4*4) min ~ 80 min.

注：我用符號~顯示近似。

O（N^2）=>使用大小爲N問題將需要大約N^2時間

M將需要大約平方公尺時間

O(M)~ O(1M) 
=> 1^2*M^2 
=> M^2 
=> 5 min 


O(4M) ~ (4M)^2 
=> 4^2*M^2 
=> 16*M^2 
=> 16*5 
=> 80 min

來源

2014-04-15 02:33:38 Ashish

通常當參考數字相對較大時，O近似值相當不錯。然而，對於小數字，事情往往不符合近似值。因此，如果算法的「M」很小（例如，* 10 *行計算機程序或具有* 50 *條目的數據庫），那麼'4M'的近似值不太可能成立。 – MooseBoys

如何概括你解決問題的方式（即大小A = X分鐘，大小B =？分鐘）並不是立即顯而易見的 - 在此添加一些細節可能是明智的。 – Dukeling

我不明白你爲什麼要計算（4 * 4）。 – user3534193

是的，這是簡單的，但你的計算是錯誤的。

你計算什麼是線性增長，例如O（n）例如如果某些輸入需要五分鐘，則將輸入的大小加倍，然後時間花費是該時間的兩倍。你聲明你的算法運行在O（n^2），這是指數增長。

所以你的計算是這樣的：

M^2 = 5 minutes <=> 
M = sqrt(5) = 2.23607 (approx)

所以

(4M)^2 = (4*2.23607)^2 = 80 minutes

這是指數式增長。

這也是爲什麼你從來不談論計算機科學的具體運行時間。是否需要5分鐘或5小時是沒有意思的。有趣的是當我們改變輸入的大小會發生什麼。因爲當我們執行的算法，我們想要的東西，運行速度更快，無論使用什麼計算機測試當輸入的大小對無限移動。

來源

2014-04-15 02:37:05 Dyrborg

如果複雜度爲O（N^2），這意味着爲大小爲N的問題的時間大約是K * N^2爲k的一些固定的，但未知的值。

如果代表的大致時間上運行爲T（N）的大小爲N的問題的算法，則在數學上你有這樣的：

T(N) = k*N^2 
T(M) = k*M^2 
T(M) = 5 minutes 
T(4*M) = k*(4*M)^2 
     = 16*k*M^2 
     = 16*T(M) 
     = 80 minutes

來源

2014-04-15 02:42:04

概括地說，不necesarily。

當我們說一個問題的時間複雜度爲O（N ），這意味着，給定大小ň的問題是什麼，它需要運行的時間大致符合形式的一些方程a + bN + cN，其中a，b和c是未知係數。

這並不意味着最終的ñ項將主導運行時間。但最終可能會很長一段時間。可能會有一個很大的固定建立時間（也就是上面的公式中的a很大），因此假設情景的5分鐘中的4個不會隨問題大小而變化。在這種情況下，大小4M的問題可能需要不到兩倍的時間才能運行。

沿着這些線條的情況可能會頻繁發生涉及散列的算法（例如某些關聯數組實現），特別是在使用諸如SHA2等慢散列函數的情況下。這就是爲什麼對於搜索簡單數組的元素的小集合來查看它是否包含元素可能比搜索哈希表更快，即使搜索數組是O（N）並且搜索哈希集合是O（1）。

來源

2014-04-15 02:59:12

你的猜測是，你有O(n)情況下是正確的，但我們有O(n^2)這意味着你需要在方恆

T(M) = (M)^2 = M^2 = 5 minutes 

T(4M) = (4 * M)^2 = 4^2 * M^2 = 16 * M^2 

Substitute: M^2 = 5 minutes 

T(4M) = 16 * M^2 = 16 * 5 minutes 

T(4M) = 80 minutes

來源

2014-04-15 09:31:43

大O和時間複雜度

回答

相關問題