-1

So I've been stuck on this problem for quite a while now and I figured, I can get some support from this community as its my last resort

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

I'm I right thinking that this has a time complexity of 0(N^2), if I'm mistaken please elaborate as this would be greatly appreciated.

Also how can I create another algorithm that computes exactly the same thing as the algorithm above but has a time complexity of 0(N)?

Thank you in advance.

4

2 回答 2

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
于 2020-03-10T22:12:10.410 回答
0
  1. 是的，您的算法的时间复杂度（上限）为 O(n^2)。每个都有两个嵌套for循环运行n时间。
  2. 在最坏的情况下，原始操作的总数lal := lal + (A[i] * B[j])为 n X n = n^2。这与第 1 点中讨论的最坏情况时间复杂度相同。

PS 你可能想阅读Thomas H. Cormen 的《算法简介》的几章。它解释了时间复杂度的基本原理。每个程序员都应该阅读这篇文章。

于 2020-03-10T19:43:41.993 回答