如何在psuedo代码上计算时间复杂度

Question

所以我已经被这个问题困扰了很长一段时间，我想，我可以从这个社区得到一些支持，作为我的最后手段

Algorithm gibby(A, B, n)

Input: arrays of integers, A and B, both of length n 
Output: integer value 
lal := 0  
for i := 0 to n-1 
for j := 0 to n-1 
lal := lal + (A[i] * B[j]) 
endfor 
endfor 
return lal 

我认为这是正确的，时间复杂度为0(N^2(，如果我错了，请详细说明，因为这将不胜感激。

此外，我如何创建另一个算法，该算法计算的内容与上面的算法完全相同，但时间复杂度为0(N(？

提前谢谢。

Answer 1

您的复杂性分析是正确的，因为您在两个数组上嵌套了两个迭代。

关于在线性时间O(N(中创建算法，您可以利用乘法和加法的数学特性。交换性、结合性和分配性使我们能够重新排序您想要进行的计算。

例如，n=4，输入数组为：

A=[a][c][e][g]
B=[b][d][f][h]

您的算法将执行以下计算：

i = 0 and j = 0..3: ab + ad + af + ah = a(b+d+f+h)
i = 1 and j = 0..3: cb + cd + cf + ch = c(b+d+f+h)
i = 2 and j = 0..3: eb + ed + ef + eh = e(b+d+f+h)
i = 3 and j = 0..3: gb + gd + gf + gh = g(b+d+f+h)

如果你采用等价的表达式，并再次简化表达式：

a(b+d+f+h) + c(b+d+f+h) + e(b+d+f+h) + g(b+d+f+h)

你得到：

(b+d+f+h)(a+c+e+g)

它是单个数组之和的乘积。这将得到相同的结果，但可以使用线性时间算法来实现。使用您的伪代码语法，算法将如下所示：

suma := 0
sumb := 0  
for i := 0 to n-1 
suma := suma + A[i] 
sumb := sumb + B[j]  
endfor 
return suma*sumb 

Answer 2

1. 是的，您的算法的时间复杂度(上限(为O(n^2(。您有两个嵌套的for循环，每个循环运行n次
2. 在最坏的情况下，基元运算lal := lal + (A[i] * B[j])的总数为n X n=n ^2。这和最坏的一样第1点中讨论的案例时间复杂性

p。S.您可能想阅读Thomas H.Cormen的算法导论中的几章。它解释了时间复杂性的基本原理。每个程序员都应该阅读这篇文章。