c++ - 随机高斯函数的时间复杂度

Question

我引用给定的 Ruby 代码 http://www.cleveralgorithms.com/nature-inspired/probabilistic/cross_entropy.html 在 C++ 中创建了交叉熵最小化方法的实现。

我无法理解 random_gaussian 函数与正态分布的关系以及它究竟在做什么。此外，我无法找出此功能的复杂性。请帮我解决这两件事。

    double random_gaussian(double mean , double stdev)
    {
          double u1,u2,w;
          do {
            u1 = 2*((double)rand()/RAND_MAX) - 1;
            u2 = 2*((double)rand()/RAND_MAX) - 1;
            w = u1*u1 + u2 * u2;
          } while( w >= 1 );

          w = sqrt(( -2.0 * log(w ))/w);
          return mean + ( u2* w ) * stdev;
    }

这是 C++ 代码 http://pastebin.com/Q4c73Kdi .该程序用于求解 AX = B，并且运行良好。

Answer 1

do...while block 在带有角 (±1, ±1) 的正方形中生成一个点，直到该点适合以原点为中心的半径为 1 的圆。预期的迭代次数是面积比，即常量 4/π，或大 O 表示法中的 O(1)。

至于这个过程和高斯分布有什么关系，是Box-Muller transform的一个应用. Here是另一个带有一些解释的页面，其中还包含您的代码。