30/09/2018, 16:35
Cách tính độ phức tạp của của thuật toán
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.
Bài liên quan
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).Lần lượt gọi số phần tử của 3 mạng là m,n,p.
Vòng
forthứ nhất chạy m lần.Vòng
forthứ 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^2Dpt= O(q*q)=O((m+n+p)^2).