計算算法時間

我有周圍冪4,500,000 2的順序非常大的數字作品的算法。我使用.NET 4中的BigInteger類來處理這些數字。計算算法時間

的算法是，它是一個單環，降低基於某些預定義的標準大的初始數目非常簡單。隨着每次迭代，數量減少約10個指數，因此在下一次迭代中4,500,000個將變爲4,499,990個。

我目前得到每秒5.16迭代或每個迭代0.193798秒。基於該算法的總時間應大致爲22小時以使指數值降至0.

問題是，隨着數量的減少，處理內存中所需的時間也減少。另外，隨着指數減少到200,000個範圍，每秒迭代次數變得巨大，並且每次迭代的減少也呈指數增長。

與其讓算法中跑了一整天，有沒有計算，將花費的時間根據初始起始編號和每秒迭代的數學方法是什麼？

這將是非常有益的，因爲我可以快速地衡量優化的嘗試改進。

考慮以下僞代碼：

double e = 4500000; // 4,500,000. 
Random r = new Random(); 
while (e > 0) 
{ 
    BigInteger b = BigInteger.Power(2, e); 
    double log = BigInteger.Log(b, 10); 
    e -= Math.Abs(log * r.Next(1, 10)); 
}

來源

2013-02-13 Raheel Khan

正在增加é？ – CR41G14 2013-02-13 11:41:15

@thang：如果我以200,000的指數值開始，算法只需要幾秒鐘來處理。該算法當然要複雜得多，但上面的代碼會產生相同的結果，因爲每次迭代的大部分時間都由BigInteger構造函數進行計算。所以你可以想象，隨着數字的減少，它會大幅加速。 – 2013-02-13 11:44:27

@ CR41G14：我的錯誤。修復了代碼。每次迭代都會減少「e」。 – 2013-02-13 11:47:03

首先重寫

double log = BigInteger.Log(b, 10);

爲

double log = log(2)/log(10) * e; // approx 0.3 * e

然後你發現，該算法Ô後終止（1）迭代（〜每次迭代70％終止的機率），你也許可以忽略除第一次迭代以外的所有成本。

算法的總成本大約是Math.Pow(2, e)的初始指數e的1至2倍。對於基地= 2，這是一個簡單的位位移，爲您需要其他方和乘法

來源

2013-02-13 12:06:28 CodesInChaos

謝謝。我會試着看看它是否接近實際的時間。 – 2013-02-13 12:09:52

-1

沒有辦法，因爲你正在使用隨機估計未知的時間！

來源

2013-02-13 11:50:23 CR41G14

實際上，隨機數僅用於代碼示例中，以將每次迭代的縮減限制在1到10之間。我很樂意使用這個級別的近似值。 – 2013-02-13 11:51:33

如果你說每次迭代都會由於這些值而發生顯着變化，那麼我不認爲這是可能的，你可以做的唯一的事情是每1000次迭代獲得一個經過的時間，並將其作爲一個非常有用的參數。 – CR41G14 2013-02-13 11:54:20

計算算法時間

回答

相關問題