为什么"Least consecutive subsequence"算法在使用hashSet时具有O(n)的运行时间复杂度？

Question

这个java代码取自极客的极客，它是为了找到最长的连续子序列，它说代码的运行时间复杂度是O(n)。但我不明白为什么 O(n) 而不是 O(n²)，因为它包含一个嵌套循环。

// Java program to find longest
// consecutive subsequence
import java.io.*;
import java.util.*;
class ArrayElements {
// Returns length of the longest
// consecutive subsequence
static int findLongestConseqSubseq(int arr[], int n)
{
HashSet<Integer> S = new HashSet<Integer>();
int ans = 0;
// Hash all the array elements
for (int i = 0; i < n; ++i)
S.add(arr[i]);
// check each possible sequence from the start
// then update optimal length
for (int i = 0; i < n; ++i)
{
// if current element is the starting
// element of a sequence
if (!S.contains(arr[i] - 1))
{
// Then check for next elements
// in the sequence
int j = arr[i];
while (S.contains(j))
j++;
// update optimal length if this
// length is more
if (ans < j - arr[i])
ans = j - arr[i];
}
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = arr.length;
System.out.println(
"Length of the Longest consecutive subsequence is "
+ findLongestConseqSubseq(arr, n));
}
}
// This code is contributed by Aakash Hasija

Answer 1

• S.contains(j)是O(1)的，因为我们知道检查哈希集中的包含是恒定的。
• j++显然是O(1).

因此，整个内循环的成本是O(1)。

因此，外循环的成本为O(n*1)=O(n)。

Answer 2

因为此条件保证它是序列的开头

if (!S.contains(arr[i] - 1))

因此，下次将不计算当前序列的所有元素。 最坏的情况是当所有元素都是连续的时。例如，[1,2,3,4,5]. 第一个元素的时间复杂度为 O(n)，其他元素的时间复杂度为 O(1)。

• n =>一次
• 1 + ... + 1 => n 次

O(n) = n + n = 2n = n