将循环转换为数学方程式

Question

我的一些程序需要有严格的时间限制才能完成给定的任务。

如果我是正确的，将某些循环转换为数学方程应该会降低我程序的时间复杂度，是吗？我可以在一次操作中得到循环找到的相同结果吗？

我已经检查了很多关于这个问题的其他解决方案，遗憾的是他们都专注于解决循环本身而不是应该采取的一般步骤将循环转换为数学方程式, 没看懂。

我需要自己转换循环，但我在互联网上找不到任何地方可以帮助解决这个问题。参考文献将不胜感激。

例如，这个循环在某些情况下需要超过 7 秒：

for (int j = 0; j < N * M; j++){
            S += V;
            V = (A * V + B) % (10007);
        }

而这个也需要超过一秒：

for (int i = 1; i <= product; i++){
    if (product % i == 0)
        sum += i;
}

请注意我的问题不在这两个循环中，我需要知道如何处理任何可转换循环。答案也不限于方程式，欢迎任何性能提示。

编辑：是我的意思的一个例子。

Answer 1

你确实可以用mathematical induction推导出一个循环等价于一个简单的公式。您链接的问题中的循环是一系列的简单总和，易于推理。然而，并非所有循环都可以简化为公式。

很难使用归纳来推理您的任何一个循环。第一个具有求余运算，使输出具有周期性。由于它是周期性的，因此单个归纳步骤不会以相同的方式应用于 j 的每个增量。证明循环存在一个简单的公式超出了我的数学技能，更不用说找到那个公式了。

我识别出你的第二个循环中的情况。测试 i 是否是 product 的因数。因此，从本质上讲，您是将一个数字的所有因数加在一起。我可以凭直觉猜测，没有简单的方法可以为此找到一个简单的公式，因为我知道没有已知的快速整数分解算法（即找到整数的所有因子）。

有比测试每个小于 product 的数字更快的算法，但对于小数字，如 int ,还不错

作为优化，您可以将迭代次数减少一半，因为我们知道没有比这更大的数字（除了 product 本身）是一个因素。 1 始终是一个因素，因此我们可以在初始化期间添加它。更进一步，我们可以添加对因子并且只迭代直到乘积的平方根：

int sum = 1 + product;
int root = sqrt(product);
for (int i = 2; i < root; i++){
    if (product % i == 0)
        sum += (i + product / i);
}
// add square root separately, because it doesn't have a pair
if (root*root == product)
    sum += root;

Answer 2

我没有时间将解决方案完全扩展为代码，但您会发现有用的想法。

第一个循环

首先我把N*M改成了N因为这样会简化方程式的书写（然后你可以代入最后的方程式以找到正确的公式）。我还将假设进入循环时 S 等于 0。我也会在外地工作 Z/10007Z（10007 是素数）

   for (int j = 0; j < N; j++){
        S += V;
        V = (A * V + B) % (10007);
    }

基本上你有一个数字序列 v_i 和一个总和 S_i 定义如下：

v_0     = ? // not important in the following equations
S_0     = 0
v_{i+1} = (A*v_i+B)
S_{i+1} = S_i + v_{i}

您可以将 v_i 的递归公式重写为矩阵运算：

|v_{i+1}|   | A  B | |v_i|
|       | = |      | |   |
|      1|   | 0  1 | |  1|

我们称M为矩阵。您现在可以通过以下公式轻松计算任何值 v_i：

|v_i|    i |v_0|
|   | = M  |   |
|  1|      |  1|

然后对 i 从 0 到 N 求和，你得到：

|S|   / N    i \ |v_0|
| | = |SUM  M  | |   |
|1|   \i=0     / |  1|

我们称矩阵M的幂和为：Q

你可以很容易地证明M的第i次方是：

 i  | A^i  B(A^i+A^(i-1)+...+1) |
M = |                           |
    | 0                       1 |

结果是：

 i  | A^i  B(1-A^(i+1))/(1-A) |
M = |                         |
    | 0                     1 |

（参见：https://en.wikipedia.org/wiki/Geometric_series#Sum）

所以我们可以将Q重写为：

    | (1-A^(N+1))/(1-A)  B*SUM(i=1,N, B(1-A^(i+1))/(1-A) ) |
Q = |                                                      |
    | 0                                                  1 |

最终我们得到：

     1   | 1-A^(N+1)  B*( N - (1-A^(N+1))/(1-A) ) |
Q = ---  |                                        |
    1-A  | 0                                    1 |

您可以在 O(log(N)) 中轻松计算 A^(N+1)。

计算1/(1-A)是根据费马小定理计算(1-A)^(10007-1-1)。

如果预先知道 A，您甚至可以预先计算它。

显然，如前所述，一切都在数字模 10007 的字段中完成。

第二个循环

基本上，您是在计算一个数的除数。我不知道有什么更好的方法。但是如果您必须对许多连续的数字执行此操作，则可能需要进行优化。

将循环转换为数学方程式

Converting loops to mathematical equations

c++

performance

loops

equation

time-complexity