TÍNH THỜI GIAN

Tinh thoi gian thuc hien chuong trinh sau;

void Bubble (int a[], int n)
{
int i, j, temp;
{1} for (i=0; i<n-1; i++)
{2} for (j=n-1; j>i; j--)
{3} if (a[j-1]>a[j])
{
{4} temp:=a[j-1];
{5} a[j-1]:=a[j];
{6} a[j]:=temp;
}
}

GIẢI
Cả 3 lệnh đổi chỗ (4)(5)(6) tốn O(1) thời gian
Vòng lăp (2) thực hiện việc đổi chỗ n-1-(i+1)+1=n-i-1 trong trường hợp xấu nhất do đó đoạn (2)và (6) tốn O((n-i+1).1)=O(n-i+1)
Vòng lặp (1) lặp n lần. Vậy độ phức tạp của giải thuật là:
(n-1)(n-1) –n(n+1)/2= O(n2)

Phải cách tínbh đoạn cuối sẽ là : Tổng(0->n-1) của (n-i+1)=Tổng(0->n-1)n-Tổng(0->n-1)i+Tổng(0->n-1)1=
=(n-1)n-n(n-1)/2+n-1=(n-1)(n-1)-n(n-1)/2
Đúng không vậy.
Nhưng mà tôi thấy nếu for(int i=0;i<=n-1;i++) thì mối làm như vậy. Chứ nếu i<n-1 thì ta không thể dùng
Tổng(0->n-1) mà phải dùng Tổng(0->n-2) chứ.

Không biết đúng hay sai. Ai biết thì chỉ nhé