算法 for(j=1;j<=n;j++) { c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; }的时间复杂度为（）。

这是一个矩阵乘法算法，矩阵A的大小为m*n，矩阵B的大小为n*p，矩阵C的大小为m*p。对于矩阵乘法的每一个元素，都需要进行n次乘法和n-1次加法，因此单次乘法的时间复杂度为O(n)，一共需要进行m * p * n次乘法和m * p * (n-1)次加法，因此总的时间复杂度为O(m * p * n)。在这个算法中，m和p都等于n，因此时间复杂度为O(n^3)。

相关问题

下列c语言程序改成python，并详细注解。#include<iostream> #include"qx.h" using namespace std; //弗洛伊德算法 void graph::floyd(graph &t, const int n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { t.a[i][j]=t.arcs[i][j]; if((i!=j)&&(a[i][j]<max)) t.path[i][j]=i; else t.path[i][j]=0; } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(t.a[i][k]+t.a[k][j]<t.a[i][j]) { t.a[i][j]=t.a[i][k]+t.a[k][j]; t.path[i][j]=t.path[k][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i!=j) { cout<<i<<"到"<<j<<"的最短路径为"<<t.a[i][j]<<":"; int next=t.path[i][j]; cout<<j; while(next!=i) { cout<<"←"<<next; next=t.path[i][next]; } cout<<"←"<<i<<endl; } } } //计算最短距离之和 void graph::add(graph &t) { int sum[n+1]; for(int i=0;i<n+1;i++) sum[i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j) { sum[i]=sum[i]+t.a[i][j]; } } cout<<endl; cout<<i<<"到各顶点的最短路径总和为"<<sum[i]<<endl; } sum[0]=sum[1]; int address=1; for(int i=2;i<n+1;i++) if(sum[0]>sum[i]) { sum[0]=sum[i]; address=i; } cout<<"所以最短路径总和为"<<sum[0]<<" 学院超市的最佳选址为顶点"<<address<<endl; } //主函数 void main() { graph t;int i,j,w; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) t.arcs[i][j]=0; else t.arcs[i][j]=max; cout<<" 学校超市最佳选址*"<<endl<<endl<<endl; cout<<"请输入请输入存在路径的两个单位以及相通两个单位间的距离(用空格隔开)"; cout<<endl; for(int k=1;k<=e;k++) { cin>>i>>j>>w; t.arcs[i][j]=w; } t.floyd(t,n); t.add(t); system("pause"); }

以下是将C语言程序改写成Python的代码，并进行注释：

class Graph:
    def __init__(self, n, e):
        self.n = n  # 图中顶点个数
        self.e = e  # 图中边的条数
        self.arcs = [[float('inf')] * (n+1) for _ in range(n+1)]  # 初始化邻接矩阵，用inf表示两点不直接相连
        self.a = [[float('inf')] * (n+1) for _ in range(n+1)]  # 存储最短距离
        self.path = [[0] * (n+1) for _ in range(n+1)]  # 存储最短路径
          
    # 弗洛伊德算法
    def floyd(self):
        for i in range(1, self.n+1):
            for j in range(1, self.n+1):
                self.a[i][j] = self.arcs[i][j]
                if i != j and self.a[i][j] < float('inf'):
                    self.path[i][j] = i
                else:
                    self.path[i][j] = 0
        
        for k in range(1, self.n+1):
            for i in range(1, self.n+1):
                for j in range(1, self.n+1):
                    if self.a[i][k] + self.a[k][j] < self.a[i][j]:
                        self.a[i][j] = self.a[i][k] + self.a[k][j]
                        self.path[i][j] = self.path[k][j]
                        
        for i in range(1, self.n+1):
            for j in range(1, self.n+1):
                if i != j:
                    print(f'{i}到{j}的最短路径为{self.a[i][j]}:', end='')
                    next = self.path[i][j]
                    print(j, end='')
                    while next != i:
                        print(f'←{next}', end='')
                        next = self.path[i][next]
                    print(f'←{i}')
    
    # 计算最短距离之和
    def add(self):
        sum = [0] * (self.n+1)
        for i in range(1, self.n+1):
            for j in range(1, self.n+1):
                if i != j:
                    sum[i] += self.a[i][j]
            print(f'{i}到各顶点的最短路径总和为{sum[i]}')
        
        address = 1
        for i in range(2, self.n+1):
            if sum[0] > sum[i]:
                sum[0] = sum[i]
                address = i
        print(f'所以最短路径总和为{sum[0]}，学院超市的最佳选址为顶点{address}')
        
if __name__ == '__main__':
    n = int(input('请输入图中顶点个数：'))
    e = int(input('请输入图中边的条数：'))
    t = Graph(n, e)
    print('学校超市最佳选址*')
    print()
    print('请输入存在路径的两个单位以及相通两个单位间的距离(用空格隔开)')
    print()
    for k in range(1, e+1):
        i, j, w = map(int, input().split())
        t.arcs[i][j] = w
    t.floyd()
    t.add()
    input('按回车键退出')

注：由于Python中列表下标从0开始，而题目中的C语言程序列表下标从1开始，因此在Python代码中需要将下标全部减1。

function SuffixArray(str) { var s = str; var n = str.length; var sa = new Array(n), rank = new Array(n), height = new Array(n), x = new Array(n), y = new Array(n), m = 256, c = new Array(m); for (var i = 0; i < m; i++) c[i] = 0; for (var i = 0; i < n; i++) c[rank[i] = s.charCodeAt(i)]++; for (var i = 1; i < m; i++) c[i] += c[i - 1]; for (var i = n - 1; i >= 0; i--) sa[--c[rank[i]]] = i; for (var k = 1; k <= n; k <<= 1) { for (var i = n - k, p = 0; i < n; i++) x[p++] = i; for (var i = 0; i < n; i++) if (sa[i] >= k) x[p++] = sa[i] - k; for (var i = 0; i < m; i++) c[i] = 0; for (var i = 0; i < n; i++) c[rank[x[i]]]++; for (var i = 1; i < m; i++) c[i] += c[i - 1]; for (var i = n - 1; i >= 0; i--) sa[--c[rank[x[i]]]] = x[i]; for (var t = rank,rank = y,y = t,p = rank[sa[0]] = 0, i = 1; i < n; i++) { rank[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p; } if (p >= n - 1) break; m = p + 1; } for (var k = i =0;i<n;++i){ if(rank[i]==0) continue; if(k) --k; var j=sa[rank[i]-1]; while(i+k<n && j+k<n && s.charAt(i+k)==s.charAt(j+k)) ++k; height[rank[i]]=k; } return { sa: sa, rank: rank, height: height }; } 这个函数创建后缀数组的能不能用DC3实现了，帮我修改为DC3算法可以吗

好的，这里是使用DC3算法实现后缀数组的代码：

function SuffixArray(str) {
var s = str;
var n = str.length;
var sa = new Array(n);
var rank = new Array(n);
var height = new Array(n);
var x = new Array(n);
var y = new Array(n);
var m = 256;
var c = new Array(m);

function sort_doubling(sa, rank, height, n, m) {
var tmp = new Array(n);
var i, j, p;
for (i = 0; i < m; ++i) c[i] = 0;
for (i = 0; i < n; ++i) c[x[i] = s.charCodeAt(i)]++;
for (i = 1; i < m; ++i) c[i] += c[i - 1];
for (i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
for (j = p = 1; p < n; j <<= 1, m = p) {
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < m; ++i) c[i] = 0;
for (i = 0; i < n; ++i) c[x[y[i]]]++;
for (i = 1; i < m; ++i) c[i] += c[i - 1];
for (i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
for (tmp[sa[0]] = 0, i = 1, p = 1; i < n; ++i) {
if (x[sa[i]] == x[sa[i - 1]] && x[sa[i] + j] == x[sa[i - 1] + j]) {
tmp[sa[i]] = p - 1;
} else {
tmp[sa[i]] = p++;
}
}
for (i = 0; i < n; ++i) x[i] = tmp[i];
if (p >= n) break;
}
for (i = 0; i < n; ++i) rank[sa[i]] = i;
for (i = j = 0; i < n; ++i) {
if (rank[i]) {
if (j) --j;
var k = sa[rank[i] - 1];
while (i + j < n && k + j < n && s.charAt(i + j) == s.charAt(k + j)) ++j;
height[rank[i]] = j;
}
}
}

function sort_triples(Y, SA, n, K) {
var i, j;
if (K <= 1) {
for (i = 0; i < n; ++i) SA[i] = i;
} else {
var t = new Array(n + 3);
for (i = 0; i < n + 3; ++i) t[i] = 0;
for (i = 0; i < n; ++i) t[Y[i]]++;
for (i = 1; i < K; ++i) t[i] += t[i - 1];
for (i = 0; i < n; ++i) SA[--t[Y[i]]] = i;
for (j = 1; j < K; ++j) {
var p = 0;
for (i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (SA[i] >= j) y[p++] = SA[i] - j;
for (i = 0; i < n + 3; ++i) t[i] = 0;
for (i = 0; i < n; ++i) t[x[i] = Y[i]]++;
for (i = 1; i < n + 3; ++i) t[i] += t[i - 1];
for (i = n - 1; i >= 0; --i) SA[--t[x[y[i]]]] = y[i];
var swap = x;
x = y;
y = swap;
p = 1;
x[SA[0]] = 0;
for (i = 1; i < n; ++i) {
var a = SA[i - 1], b = SA[i];
var cmp = ((Y[a] == Y[b]) && (Y[a + j] == Y[b + j]));
x[SA[i]] = cmp ? p - 1 : p++;
}
if (p >= n) break;
K = p;
}
}
}

function dc3(SA, s, n, K) {
var i, j, *y = new int[n + 3], * SA12 = new int[n / 3 + 1], * y12 = new int[n / 3 + 1], * SA0 = new int[n / 3], * y0 = new int[n / 3], c0, c1, c2;
s[n] = s[n + 1] = s[n + 2] = 0;
for (i = 0, j = 0; i < n; ++i) {
if (i % 3 != 0) y[j++] = i;
}
sort_triples(y, SA12, j, K);
for (i = 0; i < j; ++i) y12[SA12[i]] = i + 1;
for (i = 0, j = 0; i < n; ++i) {
if (i % 3 == 1) {
y0[j++] = i;
}
}
sort_doubling(SA0, y0, new int[j], j, K);
for (i = 0, j = 0, c0 = c1 = c2 = -1; i < n; ++i) {
if (i % 3 == 1) {
var p0 = SA0[j];
var p1 = (p0 < n - 1) ? y[p0 + 1] : -1;
var p2 = (p0 < n - 2) ? y[p0 + 2] : -1;
int cmp;
if ((cmp = (y[p0] == c0 ? y[p1] == c1 ? y[p2] == c2 ? 0 : 1 : 0 : 0)) == 1) {
SA[i] = p0;
++j;
} else {
SA[i] = n + SA12[y12[p0 / 3] + (cmp == 0 ? 0 : SA12.length)];
}
} else if (i % 3 == 2) {
var p0 = SA12[y[i / 3]];
var p1 = (p0 < n - 1) ? y[p0 + 1] : -1;
var p2 = (p0 < n - 2) ? y[p0 + 2] : -1;
int cmp;
if ((cmp = (y[p0] == c0 ? y[p1] == c1 ? y[p2] == c2 ? 0 : 1 : 0 : 0)) == 1) {
SA[i] = p0;
} else {
SA[i] = n + SA0[y0[p0 / 3] + (cmp == 0 ? 0 : SA0.length)];
}
}
}
delete[] y;
delete[] SA12;
delete[] y12;
delete[] SA0;
delete[] y0;
}

dc3(sa, s, n, m);
return {
sa: sa,
rank: rank,
height: height
};
}