Confused về Big O notation

Question

Tôi có hai câu hỏi:

public static void method1(int[] a, int[] b) { 
    int sum1 = 0, sum2 = 0; 

    for(int i = 0; i < a.length; i++) { 
     sum1 += a[i]; 
    } 

    for(int i = 0; i < b.length; i++) { 
     sum2 += b[i]; 
    } 
} 

Câu hỏi 1: Đây có phải là trong thời gian O (n)? Có vấn đề bao nhiêu vòng (không vòng lặp lồng nhau) là trong method1?

Câu hỏi 2: Nếu có một

Arrays.sort(a); 

bên trong method1, những gì chức năng là nó?

Answer 1

Câu hỏi 1: Đây có phải là O (n) không?

Chính xác (ở đây, n biểu thị độ dài của mỗi trong hai mảng).

Có quan trọng bao nhiêu vòng lặp (không phải vòng lặp lồng nhau) nằm trong phương thức 1 không?

Không, miễn là số vòng lặp được cố định và số lần lặp trong mỗi vòng lặp là tuyến tính trong n. Chính thức hơn, nếu C là một số hằng số, C*n là O(n).

Câu hỏi 2: Nếu có một Sorting Arrays.sort(a);

thường là O(n logn), và đây là những gì Arrays.sort(int[]) không trung bình. Các documentation là mơ hồ về hiệu suất trường hợp xấu nhất:

thuật toán này cung cấp O (n log (n)) thực hiện trên nhiều bộ dữ liệu gây quicksorts khác làm suy giảm hiệu suất bậc hai, và thường là nhanh hơn so với truyền thống (một trục) Triển khai Quicksort.

Điều này rõ ràng dừng ngắn đảm bảo O(n logn) trong trường hợp xấu nhất . Đọc giữa các dòng cho thấy rằng nó có thể là O(n^2).

Điều thú vị là trong JDK7, Arrays.sort(Object[]) sử dụng một thuật toán khác với thuật toán được sử dụng bởi Arrays.sort(int[]). Trước đây là một sự thích ứng của TimSort, và do đó nên đảm bảo hiệu suất trường hợp xấu nhất O(n logn). Thật không may, tài liệu một lần nữa dừng ngắn chính tả này ra.

Answer 2

1. a. Đó là O (n) trong đó n = chiều dài đầu vào (tổng cộng)
   b. Có vấn đề là có bao nhiêu vòng lặp: nếu đó là số vòng lặp k không đổi thì đó là O (k * n) thường được coi là O (n) nhưng nếu k> = n, nó sẽ được đưa vào tài khoản

2. Arrays.sort(a); được triển khai bằng cách sử dụng sắp xếp hợp nhất đang chạy trong O (n log n) cả trong trường hợp trung bình và xấu nhất (không giống như NPE đã nói!).

Cập nhật cho MrSmith42:

Từ http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html:
các thuật toán được sử dụng bởi loại (Object []) không phải là một Mergesort, nhưng nó không phải là ổn định).

Và cũng:

lưu ý thực hiện: Các thuật toán sắp xếp là một dual-P ivot Quicksort của Vladimir Yaroslavskiy, Jon Bentley và Joshua Bloch. Thuật toán này cung cấp hiệu suất O (n log (n)) trên nhiều tập dữ liệu khiến các quicksorts khác làm suy giảm hiệu suất bậc hai và thường nhanh hơn các triển khai Quicksort truyền thống (một trục).