算法的复杂性，当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循环。我想知道这个算法的复杂度是怎么计算的？

Answer 1

while 循环迭代 i 值，但它可以使用相同的值执行多次迭代。然后，辅助变量 j 递增，并达到相同的最大值。

这意味着实际上这个算法对来自给定数组 A （包括两次相同的值）。例如，如果 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 的操作不会影响时间复杂度，只会影响功能。

Answer 2

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

通过一个例子来理解这一点；我想买一辆汽车和一辆自行车。一辆汽车的价格在 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) //{记得汽车和自行车的加法}

Complexity of Algorithm,when while loop changes