小编zed*_*dai的帖子

我想出了这种矩阵乘法算法.我在某处读到矩阵乘法的时间复杂度为o(n ^ 2).但我认为我的算法会给出o(n ^ 3).我不知道如何计算嵌套循环的时间复杂度.所以请纠正我.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

我正在学习Merge排序,并且在合并步骤中遇到使用sentinel作为无限.

这是Cormen书中的算法.为什么我们在步骤8和9中使用了无穷大？

MERGE(A, p, q, r)

1 n1 ? q ? p + 1

2 n2 ? r ? q

3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]

4 for i ? 1 to n1

5 do L[i ] ? A[ p + i ? 1]

6 for j ? 1 to n2

7 do R[ j ] ? A[q + j ]

8 L[n1 + 1] ? ?

9 R[n2 + …