如何计算伪代码的时间复杂度

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^2)。您有两个嵌套 for 循环，每个循环运行 n 次。
在最坏的情况下，原始操作的总数lal := lal + (A[i] * B[j])是n X n = n^2。这和最坏的一样第 1 点中讨论的案例时间复杂度。

P.S。您可能想阅读 Thomas H. Cormen 的 Introduction to Algorithms 的几章。它解释了时间复杂度的基本原理。每个程序员都应该阅读这篇文章。

Answer 2

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

关于在线性时间 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

如何计算伪代码的时间复杂度

How to calculate time complexity on psuedo-code

java

big-o

pseudocode

time-complexity