查找整数数组中最长连续序列的长度的程序的时间复杂度是多少？

Question

谁能给我解释一下这个程序的时间复杂度是多少？

public static void main(String[] args) {
    int arr[] = { 1, 9, 3, 10, 4, 20, 2};
    ConsecutiveSequence(arr);
}

public static void ConsecutiveSequence(int []a){
    Arrays.sort(a);

    int k =1;
    int n = a.length;
    int max_length=0;
    
    for(int i =0;i<n-1;i++){
        if(a[i]+1==a[i+1]){
            k++;
            if(i==n-2){
                max_length=Math.max(max_length,k);
            }
        }else{
            max_length=Math.max(max_length,k);
            k=1;
        }
    }

    System.out.println(max_length);
}

Answer 1

时间复杂度为N log (N)。为什么？

Arrays.sort(a);

for(int i =0;i<n-1;i++){
    if(a[i]+1==a[i+1]){
        k++;
        if(i==n-2){
            max_length=Math.max(max_length,k);
        }
    }else{
        max_length=Math.max(max_length,k);
        k=1;
    }
}

操作：

Arrays.sort(a);

具有众所周知的复杂性 N log (N)。作为一个 confirm here:

This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

对于循环，您迭代 n-1 次，并且对于每次迭代，您执行常量操作。所以 (N-1) * C.

所以整体复杂度是N log (N) + (N - 1) * c。由于随着输入的增加 N log (N) 比 (N - 1) 增长得更快，复杂度可以表示为 by O(N log (N))。有关为什么可以用 O(N log (N)) 表示的更多信息，请查看 .

查找整数数组中最长连续序列的长度的程序的时间复杂度是多少？

What is the time-complexity of a program that finds the length of the longest consecutive sequence in an array of integers?

java

complexity-theory

big-o

time-complexity