Mức độ phức tạp của phân loại bong bóng

Question

Tôi đã thấy ở nhiều nơi, độ phức tạp của việc sắp xếp bong bóng là O (n).

Nhưng làm thế nào điều đó có thể như vậy vì vòng lặp bên trong phải luôn chạy n-i lần.

for (int i = 0; i < toSort.length -1; i++) { 
      for (int j = 0; j < toSort.length - 1 - i; j++) { 
       if(toSort[j] > toSort[j+1]){ 
        int swap = toSort[j+1]; 
        toSort[j + 1] = toSort[j]; 
        toSort[j] = swap; 
       } 
      } 
     } 

Answer 1

Giá trị "trung bình" là n-i là bao nhiêu? n/2

Vì vậy, nó chạy trong O(n*n/2) được coi là O (n)

Answer 2

Kể từ vòng ngoài chạy n lần và cho mỗi lần lặp chạy bên trong (ni) lần, tổng số hoạt động có thể được được tính là n * (ni) = O (n2).

Answer 3

Có nhiều loại phức tạp về thời gian khác nhau - bạn đang sử dụng ký hiệu O lớn để có nghĩa là tất cả các trường hợp của hàm này sẽ ít nhất là độ phức tạp thời gian này.

Khi tiếp cận vô cùng, điều này có thể về cơ bản là trường hợp xấu nhất trong trường hợp xấu nhất 2 lần. Độ phức tạp về thời gian không phải là một nghệ thuật chính xác mà còn là một sân chơi bóng chày cho loại tốc độ mà bạn có thể mong đợi cho lớp thuật toán này và do đó bạn đang cố gắng quá chính xác.

Ví dụ: độ phức tạp về thời gian lý thuyết có thể rất tốt là n^2 mặc dù lý thuyết có thể là n * n-1 vì bất kỳ chi phí xử lý không lường trước nào có thể được thực hiện.

Answer 4

Đó là O (n^2), vì độ dài * chiều dài.