Cách tính độ phức tạp của của thuật toán

[14520054 (BaoLe)]

Mình có hàm NoiMang như bên dưới, hàm này sẽ nối 2 mảng truyền vào hàm lại với nhau và sau đó sắp xếp theo thứ tự tăng dần.

void NoiMang(int Mang_1[], int SoPhanTu_1, int Mang_2[], int SoPhanTu_2, int Mang_3[], int &SoPhanTu_3){
	//Sao chep toan bo noi dung cua Mang_1 vao Mang_3, gia tri cua SoPhanTu_3 luc dau = 0.
	for(int i = 0; i < SoPhanTu_1; i++)
		Mang_3[SoPhanTu_3++] = Mang_1[i];
	//Sao chep toan bo noi dung cua Mang_2 vao Mang_3(Ghi vao cuoi).
	for(int i = 0; i < SoPhanTu_2; i++)
		Mang_3[SoPhanTu_3++] = Mang_2[i];
	//Sap xep Mang_3 theo thu tu tang dan.
	for(int i = 0; i < SoPhanTu_3 - 1; i++)
		for(int j = i + 1; j < SoPhanTu_3; j++)
			if(Mang_3[i] > Mang_3[j]){
				int tam = Mang_3[i];
				Mang_3[i] = Mang_3[j];
				Mang_3[j] = tam;
			}
}

Nhờ mọi người chỉ mình cách tính độ phức tạp của đoạn chương trình trên với.

[Byn]

Gọi số phần từ mảng 1 là n, màng 2 là m, khi đó độ phức tạp là O((n*m)^2).

[Gio (Gió)]

Lần lượt gọi số phần tử của 3 mạng là m,n,p.
Vòng for thứ nhất chạy m lần.
Vòng for thứ hai chạy n lần.
Số phần tử của mảng 3 là: m+n+p, thay bằng biến q=m+n+p.

Đoạn sắp xếp chạy vòng for 1 q lần vòng for 2 chạy i lần với i=1…q-1
Như vậy tổng lần chạy trong đoạn sắp xếp là: q*(q-1)/2
Ta có m,n,p<q<q^2
Dpt= O(q*q)=O((m+n+p)^2).