Một công cụ để tính toán độ phức tạp thời gian lớn của mã Java?

Question

Tôi có một câu hỏi liên quan đến sự phức tạp về thời gian (ký hiệu O lớn) cho phần mềm Java. Có cách nào để nhanh chóng tính toán hoặc kiểm tra nó (hoặc bất kỳ trang web có thể tính toán nó cho tôi sẽ được hoan nghênh). Ví dụ tôi muốn kiểm tra xem nó cho đoạn mã sau đây và có thể cải thiện cũng như:

int dcount = 24423567; 
     int a = 0; 
     if (dcount == 0){ 
      a = 1; 
     } 

     String ds = Integer.toString(dcount); 
     String[] sa = ds.split("(?<=.)"); 
     HashSet hs = new HashSet(); 
     Collections.addAll(hs, sa); 
     a = hs.size(); 
     if (dcount < 0) 
      a--; 

     System.out.println(a); 

Answer 1

Như @emory chỉ ra, nó là provably không xác định được thời gian phức tạp lớn-O của một mảnh tùy ý mã tự động (bằng chứng là giảm từ Halting Problem). Tuy nhiên, có những công cụ có thể cố gắng đo lường sự phức tạp của một đoạn mã theo kinh nghiệm bằng cách chạy nó trên một số đầu vào khác nhau. Một công cụ như vậy được mô tả trong bài báo “Đo lường tính phức tạp tính toán thực nghiệm” của Goldsmith, Aiken và Wilkerson. Nó hoạt động bằng cách cố gắng thực hiện hồi quy về thời gian chạy của chương trình so với kích thước đầu vào của chương trình. Công cụ này, được gọi là trend-prof, có sẵn trực tuyến.

Hy vọng điều này sẽ hữu ích!

Answer 2

tôi có thể giải quyết các bài tập về nhà của một ai đó, nhưng câu hỏi đã cầu xin cho một giải pháp lành mạnh ...

Đếm chữ số riêng biệt trong một số đòi hỏi không dây, bộ hoặc biểu thức thông thường, chỉ cần một số arithmetics đơn giản.

Các phương pháp sau đây chạy trong thời gian O (n) thời gian (n = số chữ số ở đầu vào) và không gian liên tục:

int distinctDigits(int num) { 
    if (num == 0) { 
    return 1; 
    } 

    boolean[] digits = new boolean[10]; 

    while (num > 0) { 
    digits[num % 10] = true; 
    num /= 10; 
    } 

    int count = 0; 
    for (boolean digit : digits) { 
    if (digit) { 
     count++; 
    } 
    } 

    return count; 
} 

Làm tác phẩm này với số âm là trái như một exericse cho người đọc;)