隨機分量算法的時間複雜度（Gillespie算法）

我試圖找到Gillespie算法的時間複雜度。隨機分量算法的時間複雜度（Gillespie算法）

通用算法可以發現：Here

更多擴展版本：Here

的假設是，反應的數目和蛋白質的數目是恆定的。這可以讓我通過單獨的時間變量來計算時間複雜度。

但是，由於時間增加，每次迭代都基於隨機值，所以我陷入困境。讓我詳細說明（刪除不相關的代碼）：

所以這是一般的循環，每次迭代反應被更新，然後currentTime被更新。

currentTime = 0.0; 
while(currentTime < timeEnd) 
{ 
    reactions->calcHazard(); 
    currentTime += this->getNextTime(); 
}

函數getNextTime計算新時間。

double Gillespie::getNextTime() 
{ 
    double randVal; 

    randVal = ((double) rand()/(double)(RAND_MAX)); 
    while (randVal == 0) 
    { 
     randVal = ((double) rand()/(double)(RAND_MAX)); 
    } 
    return ((1.0/reactions->getSum())*(log(1.0/randVal))); 
}

新時間大小的計算是基於一個隨機值R.這裏的另一個變量組件是反應結果 - > getsum。該函數的返回值是

sum(k*A(t))

其中K和A（t）爲兩個矢量，k是用於每個反應和A（t）的概率是蛋白質中的時間t的數量。

有關時間增加的更好解釋可能由上一個鏈接的第7頁提供。

是否有可能對此的時間複雜性（tStart - > tEnd迭代）說些什麼？或者，如果不包括有關#proteins和#reactions的信息，這是不可能的？

來源

2015-01-12 Dwarrel

這是O(n)。您並不需要計算getNextTime()的預期回報值。知道它的回報不會因模擬運行而改變就足夠了。

讓我們假設你的代碼迭代循環N次爲1 hour模擬。

這是很明顯，這些都是等價...

timeEnd = currentTime + 2hours; 
while (currentTime < timeEnd) { ... } // ??? iterations

相當於

timeMid = currentTime + 1hour; 
timeEnd = currentTime + 1hour; 
while (currentTime < timeMid) { ... } // N iterations 
while (currentTime < timeEnd) { ... } // <=N iterations

所以，迭代循環大約2N次爲一2 hour模擬。

的假設是，反應的數目和蛋白質的數量是恆定的

即有用的假設。基本上，這意味着getNextTime()不會隨着模擬運行而系統地增加或減少。如果在仿真過程中返回值getNextTime()減少（意味着A（t）在仿真過程中增加），那麼第二個循環將比第一個迭代花費更多的迭代次數。

無論如何，如果系統在某個點達到平衡點（這是不可避免的，對嗎？我不是化學家），你或許可以做出這樣的假設。因爲那麼A（t）是恆定的，因爲那是......平衡是什麼。

來源

2015-01-12 22:39:49 QuestionC

我可能錯誤地製造了蛋白質的數量。不同蛋白質的數量不會改變。然而，每種蛋白質的量確實會增長或收縮。程序的輸入是（T，P，R，Rc），其中T =時間，P =不同蛋白質的數量，R =可能的反應及其相應的反應變化。所以A（t）總是能夠改變的，我不能假設一個均衡是永遠實現的。它也可能處於振盪狀態。但是我認爲你對於更大的N（endtime）是正確的，每次迭代所需的工作量保持不變！錯過了那個，ty – Dwarrel

隨機分量算法的時間複雜度（Gillespie算法）

回答

相關問題