如何计算 while 循环的大 O 时间复杂度

Question

我无法理解 while 循环如何影响 Big O 时间复杂度。

例如，我将如何计算下面代码的时间复杂度？因为它有一个遍历数组中每个元素的 for 循环和两个嵌套的 while 循环，我最初的想法是时间复杂度为 O(n^3)，但我认为这是不对的。

HashMap<Integer,Boolean> ht = new HashMap<>();

for(int j : array){
      if(ht.get(j)) continue;

      int left = j-1;
      //check if hashtable contains number
      while(ht.containsKey(left)){
        //do something
        left--;
      }

      int right = j+1;
      //check if hashtable contains number
      while(ht.containsKey(right)){
        //do something
        right++;
      }

      int diff = right - left;
      if(max < diff) {
        //do something
      }
}

Answer 1

对于一个嵌套循环，时间复杂度如下：O(n^2)。

在 i 的每次迭代中，内部循环执行 'n' 次。一个循环的时间复杂度等于最里面语句要执行的次数。

所以你的情况是 O(n^2)+O(n)。

在那里你可以找到更多的解释

Time-complexity

Answer 2

假设您的 HashMap 和 array 中分别有 m 和 n 条目。

因为 for 循环有 n 个元素，复杂度可以写成 n * complexity_inside_for.

在 for 循环中，您有两个连续的（未嵌套的）while 循环，每个循环的复杂度为 m，因为在最坏的情况下它需要经过HashMap 中的所有条目。因此，complexity_inside_for = m + m = 2m.

总的来说，时间复杂度是n * 2m。但是，随着 m 和 n 接近无穷大，数字 2 并不重要，因为它不是 m and/or n 的函数并且可以丢弃。这给出了 O(m*n)

的 big-O 时间复杂度

Answer 3

有最佳情况、平均情况和最坏情况。

我将不得不假设有一些东西限制了两个 while 循环，因此它们都不会迭代超过 n 次，其中 n 是元素的数量在数组中。

在最好的情况下，你有 O(n)。那是因为 if(ht.get(j)) 总是 true，总是采用 continue 路径。 while 循环都没有执行。

对于最坏的情况，if(ht.get(j))总是false，while循环将被执行。此外，在最坏的情况下，每个 while 循环将有 n 遍。 [1] 两个内部循环的最终结果是 2 * n 乘以外部循环的 n：(2 * n) * n。那会给你 O(n^2) 的时间复杂度。 [2]

查找时间可能是一个因素。散列 table 查找通常以恒定时间运行：O(1)。那是最好的情况。但是，最坏的情况是 O(n)。当所有条目都具有相同的哈希码时，就会发生这种情况。如果发生这种情况，它可能会将您的最坏情况更改为 O(n^3)。

[1]我怀疑最坏的情况，第一个while循环的遍数加上第二个while循环的遍数其实是n还是接近给它。但是，这不会改变结果。

[2] 在大O中，我们选择增长最快的项，忽略系数。因此，在此示例中，我们将 2 放入 2*n*n.

如何计算 while 循环的大 O 时间复杂度

How to calculate Big O time complexity for while loops

java

big-o

for-loop

while-loop