algorithm - 您如何将代码表示为用于运行时分析的数学算法？

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++) .

同理

意味着我们必须对矩阵中的每个元素执行此操作，它转换为(对于维度为 n*m 的基于 0 的矩阵):

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

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

• 矩阵中位置的2个循环
• 求和的 1 个循环