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

Question

这段java代码取自geeks for geeks，寻找最长的连续子序列，代码的运行时间复杂度为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

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

Why "Least consecutive subsequence" algorithm have O(n) running time complexity when we are using hashSet?

java

algorithm

big-o

set