时间戳

首页 > 解决方案 > 在整数数组中找到最长连续序列的长度的程序的时间复杂度是多少？

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

问题描述

有人可以向我解释这个程序的时间复杂度是多少吗？

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);
}

标签： javatime-complexitybig-ocomplexity-theory

解决方案

时间复杂度为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)。正如这里确认的那样：

该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

对于循环，您迭代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))请查看这个 SO Thread。

推荐阅读