hiệu suất của int Array vs Integer Array

Question

Hôm nay khi tôi gửi một giải pháp cho codeforces, tôi đã sử dụng int [] mảng và gửi của tôi có TLE (Thời gian vượt quá giới hạn) & sau khi thay đổi nó thành Integer [] mảng đáng ngạc nhiên nó có AC. Tôi đã không nhận được hiệu suất được cải thiện như thế nào.

import java.io.*; 
import java.lang.reflect.Array; 
import java.util.*; 

public class Main { 
    static class Task { 
     public void solve(InputReader in, PrintWriter out) throws Exception { 
      int n = in.nextInt(); 
      Integer[] a = new Integer[n]; 
      for (int i = 0; i < n; i++) a[i] = in.nextInt(); 
      Arrays.sort(a); 
      long count = 0; 
      for (int i = 0; i < n; i++) count += Math.abs(i + 1 - a[i]); 
      out.println(count); 
     } 
    } 

    public static void main(String[] args) throws Exception{ 
     InputStream inputStream = System.in; 
     OutputStream outputStream = System.out; 
     InputReader in = new InputReader(inputStream); 
     PrintWriter out = new PrintWriter(outputStream); 
     Task task = new Task(); 
     task.solve(in, out); 
     out.close(); 
    } 


    static class InputReader { 
     public BufferedReader reader; 
     public StringTokenizer tokenizer; 

     public InputReader(InputStream stream) { 
      reader = new BufferedReader(new InputStreamReader(stream), 32768); 
      tokenizer = null; 
     } 

     public String next() { 
      while (tokenizer == null || !tokenizer.hasMoreTokens()) { 
       try { 
        tokenizer = new StringTokenizer(reader.readLine()); 
       } catch (IOException e) { 
        throw new RuntimeException(e); 
       } 
      } 
      return tokenizer.nextToken(); 
     } 

     public int nextInt() { 
      return Integer.parseInt(next()); 
     } 

    } 
} 

Answer 1

Lý do khá đơn giản: độ phức tạp của giải pháp với Integer là tốt hơn.

Âm thanh lạ, phải không?

Arrays.sort sử dụng phân loại nhanh kép cho nguyên thủy, hoạt động trong thời gian xấu nhất là O(N^2). Các trường hợp thử nghiệm giải pháp của bạn không thành công là một thử nghiệm phân loại chống nhanh chóng được xây dựng đặc biệt.

Tuy nhiên, phiên bản dành cho đối tượng sử dụng sắp xếp hợp nhất, chạy trong thời gian O(N * log N) cho bất kỳ đầu vào nào có thể. Lưu ý rằng nó không phải là một phần của đặc tả ngôn ngữ Java (nó không nói cách thức sort nên được thực hiện), nhưng nó hoạt động như thế này trong hầu hết các triển khai thực sự (ví dụ, nó là trường hợp cho openjdk-8)

PS Những điều như thế này xảy ra thường xuyên hơn hoặc ít thường xuyên hơn trong lập trình cạnh tranh, vì vậy tôi khuyên bạn nên sắp xếp các mảng đối tượng hoặc sử dụng các bộ sưu tập.