algorithm - 算法的复杂性，当while循环改变时

Question

该算法将数组作为输入。

i=1
j=1
m=0
c=0
while i<=|A|
   if A[i] == A[j]
      c=c+1
   j=j+1
   if j>|A|
     if c>m
       m=c
     c=0
     i=i+1
     j=i
return m

据我所知，while 循环的复杂度是 O(n)。但我无法理解这个算法和while循环。我需要知道这个算法的复杂度是如何计算的？

score 1 · Accepted Answer

while循环对i值进行迭代，但它可以使用相同的值执行多次迭代。然后，次要变量j会增加，并运行到相同的最大值。

这意味着实际上该算法会针对给定数组A中的 2 个值（i和j ）的每个（无序）组合循环（包括两次相同的值）。例如，如果A为 [1, 2, 3, 4]，则i和j在循环的每次迭代中取这些值：while

  i  |  j
-----+-----
  1  |  1
  1  |  2
  1  |  3
  1  |  4
  2  |  2
  2  |  3
  2  |  4
  3  |  3
  3  |  4
  4  |  4

如果我们将n定义为A中值的数量，则while循环迭代n(n+1)/2次。在上面的例子中：4*5/2 = 10 次。

这是½n²+½n = O(n²)。

请注意，代码中变量c和m的操作不会影响时间复杂度，只会影响函数的结果。

score 0 · Accepted Answer

最慢的过程决定了任何过程所花费的时间。

用一个例子来理解这一点；我想买一辆汽车和一辆自行车。汽车的价格在 100000 美元左右，自行车的价格是 1000 美元。当我添加它们时，我得到了 101000 美元这里出现了一个问题；什么决定了两者的成本？当然，汽车是决定因素。在这种情况下，我们经常会忽略自行车的价格。

循环所花费的时间比声明一些变量或一些算术运算所花费的时间要多，因为这个循环可能会运行数十亿次。

i=1
j=1
m=0
c=0

这部分需要一个单位的时间。

虽然，这整个代码-->

while i<=|A|
   if A[i] == A[j]
      c=c+1
   j=j+1
   if j>|A|
     if c>m
       m=c
     c=0
     i=i+1
     j=i

将运行 N 次，其中 N 是数组的长度。

类似地，这些赋值和条件操作将花费 O(1) 时间。

添加它们会给你

O(1) + O(N)= O(N) //{ 记得添加汽车和自行车}

2 回答 2