i m tính toán thời gian chạy cho thuật toán này?Thời gian chạy (lớn O)) của thuật toán
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?
Có, hóa ra là 'O (n^2) 'là chi phí của loại bong bóng mà bạn đang làm ở đây ... mà bạn có thể tìm thấy bằng cách googling tên của thuật toán và đi vào kết quả. http://en.wikipedia.org/wiki/Bubble_sort –
tôi đã kiểm tra nhưng tôi đã có một nghi ngờ trong đó, đó là lý do tại sao tôi đăng. –