OlveraeUNSW
返回题目列表
COMP2521

复杂度 · 矩阵乘法的乘法次数

复杂度 · N×N 矩阵乘法做多少次标量乘法(2521 21T3 真题)

两个 N×N 矩阵相乘,朴素三重循环算法一共要做多少次标量乘法?读入 N,输出这个次数。

请补全 matMultCount。

关键推导:结果矩阵有 N×N 个元素;每个元素是「一行点乘一列」,需要 N 次乘法。所以总数 = N × N × N = N³。这就是矩阵乘法 O(n³) 的来历。N = 3 时是 27 次(正是 21T3 Q1 的答案)。

输入

  • 一行:整数 N(0 ≤ N ≤ 1000)。

输出

  • 一行:标量乘法次数 N³。

示例:输入 3 → 输出 27。

样例

stdin
3
期望输出
27
stdin
2
期望输出
8
c-dcc
14