具有随机成分的算法的时间复杂度（Gillespie 算法）

Question

我正在尝试找出 Gillespie 算法的时间复杂度。

通用算法可以查到：Here

更多扩展版本：Here

假设是反应的数量和蛋白质的数量是恒定的。这可能允许我单独通过时间变量来计算时间复杂度。

但是我卡住了，因为每次迭代的时间增加都是基于一个随机值。让我详细说明（删除了不相关的代码）：

所以这是一般循环，每次迭代更新反应，然后更新当前时间。

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。这里的另一个变量成分是reactions->getsum的结果。这个函数的return值为

sum(k*A(t))

其中 k 和 A(t) 都是向量，k 是每个反应的概率，A(t) 是时间 t 的蛋白质数量。

之前 link 的第 7 页可能会提供有关时间增加的更好解释。

是否可以说说这个（从 tStart -> tEnd 迭代）的时间复杂度？或者如果不包括有关#proteins 和#reactions 的信息，这是不可能的吗？

Answer 1

是O(n)。您实际上不需要计算 getNextTime() 的预期 return 值。知道它的 return 不会响应模拟运行.

就足够了

让我们假设您的代码迭代该循环 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

因此，它为 2 hour 模拟迭代循环约 2N 次。

The assumption is that the number of reactions and the number of proteins is constant

这是有用的假设。基本上，这意味着 getNextTime() 不会随着模拟运行而系统地增加或减少。如果 getNextTime() 的 return 值在模拟过程中减少（意味着 A(t) 在模拟过程中增加），那么第二个循环将比第一个循环需要更多的迭代。

如果系统在某个点达到平衡，你可能无论如何都可以做出这个假设（这是不可避免的，对吧？我不是化学家）。因为那时 A(t) 是常数，因为那是……平衡是什么。

具有随机成分的算法的时间复杂度（Gillespie 算法）

Time complexity of algorithm with random component (Gillespie Algorithm)

c++

algorithm

random

complexity-theory

time-complexity