如何将代码表示为运行时分析的数学算法？

Question

假设我已经为矩阵乘法编写了一个小循环：

array1[2][2] = {
   {1, 2},
   {3, 4}
};
array2[2][2] = {
   {5, 6},
   {7, 8}
};
arrayOutput[2][2] = {
   {0, 0},
   {0, 0}
};

for (int x = 0; x < 2; x++){
    for (int y = 0; y < 2; y++){
        for (int z = 0; z < 2; z++){
            arrayOutput[x][y] += array1[x][z] * array2[z][y];
        }
    }
}

如何将其分解为用于计算运行时间的数学算法（一般而言，不仅仅是这一特定代码块的步骤）？

我已经阅读了很多关于如何将给定的数学算法分解为运行时分析的最主要组件的材料，但是我还没有找到一个简单的解释，说明如何在这个数学表达式中得到一个块代码事实上，我发现很难看到一大块代码与其数学表达式之间的关系;它们通常看起来相当远，我并不完全掌握哪些数学符号与基本编程概念相关。

请像我5岁那样解释，或者如果可能的话，将其分解为简单的步骤;我可能一直在寻找有用的资源，只是不了解它们。

Answer 1

翻译成

result = 0;
for (int i = a; i <= b; i++) {
    result = result + ...;
}

除了运算符和结果的初始化之外基本相同，因为乘法的中性元素是1而不是0的总和，所以它转换为

result = 1;
for (int i = a; i <= b; i++) {
    result = result * ...;
}

当我们讨论矩阵或向量的索引并且具有基于0的数组的编程语言时，我们必须减去一个，因为在数学中，向量中的第一个元素具有索引1而不是0.因此代码将变为for (int i = a - 1; i < b; i++)。

同样

意味着我们必须为矩阵中的每个元素执行它并转换为（对于基于0的矩阵，其维数为n * m）：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        c[i][j] = ...;
    }
}

这就解释了为什么在矩阵乘法示例中得到3个循环：

• 2个循环用于矩阵中的位置
• 1个循环的总和