Thời gian chạy (lớn O)) của thuật toán

Question

i m tính toán thời gian chạy cho thuật toán này?

       Cost  No Of Times 

for(j=1;j<=n-1;j++){   c1  n(loop will run for n-1 times +1 for failed cond    

    for(i=0;i<=n-2;i++){  c2  n*(n-1) (n-1 from outer loop and n for inner 

     if(a[i]>a[i+1]){  c3  (n-1)*(n-1) 

      Swap    c4  (n-1)*(n-1) {in worst case } 
     } 
    } 

trong trường hợp xấu nhất T (n) = c1 * n + c2 * (n-1) n + c3 (n-1) (n-1) + c4 * (n 1) (n-1) mà là O (n^2)

Trong trường hợp xuất sắc nhất:

T (n) = c1 * n + c2 * (n-1) n + c3 (n-1) (n-1) là O (n^2).

NHƯNG thực sự trong trường hợp tốt nhất sắp xếp bong bóng có độ phức tạp về thời gian O (n). Có ai giải thích được không?

Answer 1

Sắp xếp bong bóng có độ phức tạp thời gian O (n) trong trường hợp tốt nhất vì có thể chuyển danh sách đã được sắp xếp vào nó.

Bạn phải kiểm tra xem bạn có thực hiện bất kỳ hoán đổi nào sau vòng lặp lồng nhau thứ hai hay không. Nếu không có trao đổi được thực hiện, danh sách được sắp xếp và không cần phải tiếp tục, vì vậy bạn có thể phá vỡ vòng lặp.

Đối với danh sách đã được sắp xếp, bạn đã lặp lại tất cả các phần tử n một lần trong trường hợp này.

Answer 2

algo của bạn để thực hiện các bong bóng sắp xếp là đúng nhưng không hiệu quả,

// n là tổng số elments

do{ 

    swp = false // swp checks whether or not any variable has been swapped 
         in the inner loop 

     for(i=0;i<=n-2;i++){ 

        if(a[i]>a[i+1]) 

        { 
         swap(a[i],a[i+1]) 

         sw = true 
        } 
     n = n-1    
    }while(sw == true && n>0) 

swp là một biến mà kiểm tra xem đã có bất kỳ trao đổi trong vòng lặp bên trong hay không,
nếu không có bất kỳ trao đổi nào, điều này có nghĩa là mảng của chúng tôi được sắp xếp.

Trường hợp tốt nhất cho bong bóng sắp xếp là khi các yếu tố đã được sắp xếp theo thứ tự tăng dần (trong trường hợp này)
mà vòng lặp bên trong chỉ chạy một lần nhưng nếu điều kiện (trong vòng lặp bên trong) là không bao giờ hài lòng và swp vẫn sai và do đó chúng tôi thoát khỏi vòng lặp bên ngoài sau một lần lặp cho bong bóng loại O (n) phức tạp.

Answer 3

Bạn có thể tính toán số lượng lặp đi lặp lại (những gì bên trong vòng lặp là không thích hợp vì nó là thời gian liên tục) sử dụng Sigma Notation:

Bubble Sắp xếp với một trường hợp tốt nhất thời gian chạy thực sự là một phiên bản nâng cao của thuật toán sắp xếp này.

Trong lần phân tích đầu tiên (vòng ngoài), nếu không có trao đổi được thực hiện, đó là thông tin quyết định rằng mảng được sắp xếp và là vô nghĩa để bao gồm tất cả các trường hợp.

Do đó, các vòng ngoài sẽ lặp một lần, và vòng lặp bên trong sẽ lặp n lần: đó là n + 1 lần lặp tổng thể ==>O (n).