Code:
// tim do phuc tap cua thuat toan heap sort
void nhapmang(int A[],int n){ {1}
for (int i=0;i>n;i++){ O(n) //thuc hien n buoc
cout<<"phan tu thu A["<<i<<"]="; O(1)
cin>>A[i]; O(1)
}
}
ket thuc lenh {1}: T(n)= O(1.n)= O(n)
void xuatmang(int A[],int n){ {2}
cout<<"endl;
for(int i=0;i>n;i++) O(n) //thuc hien n buoc
cout<<A[i]<<"\t"; O(1)
}
ket thuc lenh {2}: T(n)= O(1.n)= O(n)
void swap(int &a,int &b){ {3}
int temp = a; O(1)
a=b; O(1)
b=temp; O(1)
}
ket thuc lenh {3}: T(n)=O(1)
void heapify(int A[],int n,int i){ {4}
int left=2*(i+1)-1; O(1)
int right=2*(i+1); O(1)
int largest;
if(left<n && A[left]>A[i]) O(1)
largest=left; O(1)
else largest =i; O(1)
if(right<n && A[right]>A[largest]) O(1)
largest =right; O(1)
if (i!=largest){ O(1)
swap(A[i],A[largest]); O(1)
heapify(A,n,largest); O(1)
}
}
ket tuc lenh {4}: T(n)= O(1)
void buildheap(int A[],int n){ {5}
for(int i=n/2-1;i>=0;i--) O(n/2) //thuc hien n/2 buoc
heapify(A,n,i); O(1)
}
ket thuc lenh {5}: T(n)= O(1.n/2)= O(n/2)
void heapsort(int A[],int n){ {6}
buildheap(A,n);
for(int i=n-1;i>0;i--){ O(n)
swap(A[0],A[i]); O(1)
heapify(A,n,0); O(1)
}
}
ket thuc lenh {6}: T(n)= O(1.n)=O(n)
Vay do phuc tap cua chuong trinh: T(n)= O(max(n,n,1,1,n/2,n))= O(n)