算法复杂度最小值和最大值

Question

我有一个问题..我有一个算法

procedure summation(A[1...n])
s=0
for i= 1 to n do
     j=min{max{i,A[i],n^3}
     s= s + j
return s

我想使用渐近符号 θ 找到该算法的最小和最大输出。关于如何做到这一点的任何想法？我必须了解算法的什么才能理解它的复杂性？

Answer 1

如果您想了解大 O 表示法或时间复杂度的工作原理？您可能想查看以下帖子 What is a plain English explanation of "Big O" notation? .

对于您展示的伪代码，复杂度为 O(n)。 n 是数组的长度。通常你可以通过查看算法有多少嵌套循环来确定复杂性。当然，情况并非总是如此，但这可以用作经验法则​​。

在下面的例子中:

procedure summation(A[B1[1...n],B2[1...n],...,Bn[1...n]])
s=0
for i= 1 to n do
    for j= 1 to m do
     j=min{max{i,A[i,j],n^3}
     s= s + j
return s

复杂度为 O(n·m)。 (所有数组的长度 b -> m)

最好或最坏的情况

对于您展示的算法，没有最好或最坏的情况。它总是对同一个数组同时运行，对运行时间的唯一影响是数组的长度。

下面是一个可能是最好或最坏情况的示例。假设您需要在数组中找到特定数字的位置。如果您的方法是从头到尾遍历数组。最好的情况是数字在开头。最坏的情况是数字排在最后。

有关更详细的说明，请查看链接。干杯。