2.Đánh Giá độ Phức Tạp Của Giải Thuật Sắp Xếp Bằng Phương Pháp ...

Tải bản đầy đủ (.doc) (11 trang)

1. Trang chủ
>>
2. Luận Văn - Báo Cáo
>>
3. Công nghệ thông tin

2.Đánh giá độ phức tạp của giải thuật sắp xếp bằng phương pháp chèn(Insertion Sort)

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (621.67 KB, 11 trang )

PHẦN A: NỀN TẢNG LÝ THUYẾT1. Mô tả chức năng và yêu cầu1.1.Khái quát về sắp xếp:Để thuận tiện và giảm thiểu thời gian thao tác mà đặc biệt là để tìm kiếmdữ liệu dễ dàng và nhanh chóng,thong thường trước khi thao tác thì dữ liệutrên mảng,trên tập tin đã có thứ tự.Do vậy thao tác sắp xếp dữ liệu là mộttrong những thao tác cần thiết và thường gặp trong quá trình lưu trữ,quản lýdữ liệuCó rất nhiều cách sắp xếp dữ liệu,nhưng ở đây ta chỉ quan tâm đến 2 thuậttoán là sắp xếp bằng phương pháp chèn (Insertion Sort) và sắp xếp dựa trênsự phân hoạch (Quick Sort).Ta sẽ đi phân tích hai thuật toán sắp xếp này đểso sánh và đánh giá độ phức tạp của chúng.1.2.Mục tiêu của bài toán:Phân tích,đánh giá và so sánh độ phức tạp(trên lý thuyết) và so sánh thờigian tính toán(trên thực nghiệm) của 2 giải thuật.2. Đánh giá độ phức tạp của giải thuật sắp xếp bằng phương pháp chèn(Insertion Sort)2.1.Ý tưởng thuật toán:Giả sử ta có dãy a1, a2, …, an trong đó i phần tử đầu tiên a1, a2, …, ai đã có thứtự. Ý tưởng của thuật toán là tìm vị trị thích hợp và chèn phần tử ai+1 vào dãy đã có thứ tự trên để có được một dãy mới có thứ tự. Cứ thế, làm đến cuối dãy ta sẽ được một dãy có thứ tự.Với dãy ban đầu a1, a2, …, an ta có thể coi đoạn chỉ có một phần tử a1 là một đoạn đã có thứ tự, sau đó ta chèn phần tử a2 vào dãy a1 để có dãy a1a2 có thứ tự. Tiếp đó, ta lại chèn phần tử a3 vào dãy a1a2 để có dãy a1a2a3 có thứ tự. Cứ thế, đến cuối cùng ta chèn phần tử an vào dãy a1a2…an-1 ta sẽ được dãy a1a2…an có thứ tự.Insertion Sort và Quick Sort Trang 12.2.Cài đặt thuật toánvoid insertionsort(int a[],int n){int pos,x;for(int i=0;i<n-1;i++){x=a[i+1];pos=i;while(pos>=0 && a[pos]>x){a[pos+1]=a[pos];pos--;}a[pos+1]=x;}}2.3.Đánh giá độ phức tạp:Ta thấy các phép so sánh xảy ra trong vòng lặp nhằm tìm vị trí thích hợp posđể chèn x. Mỗi lần so sánh mà thấy vị trí đang xét không thích hợp, ta dời phầntử a[pos] sang phải.Ta cũng thấy số phép gán và số phép so sánh của thuật toán phụ thuộc vàotình trạng của dãy ban đầu. Do đó ta chỉ có thể ước lượng như sau:2.3.1. Trường hợp tốt nhất: Dãy ban đầu đã có thứ tự. Ta tìm được ngayvị trí thích hợp để chèn ngay lần so sánh đầu tiên mà không cần phảivô vòng lặp. Như vậy, với i chạy từ 2 đến n thì số phép so sánh tổngcộng sẽ là n-1. Còn với số phép gán, do thuật toán không chạy vàovòng lặp nên xét i bất kỳ, ta luôn chỉ phải tốn 2 phép gán(x = a[i] vàa[pos] = x). Từ đây, ta tính được số phép gán tổng cộng bằng 2(n - 1).2.3.2. Trường hợp xấu nhất:Dãy ban đầu có thứ tự ngược. Ta thấy ngayvị trí thích hợp pos luôn là vị trí đầu tiên của dãy đã có thứ tự, và doInsertion Sort và Quick Sort Trang 2đó, để tìm ra vị trí này ta phải duyệt hết dãy đã có thứ tự. Xét i bất kỳ,ta có số phép so sánh là i-1, số phép gán là (i - 1) + 2 = i + 1. Với ichạy từ 2 đến n, ta tính được số phép so sánh tổng cộng bằng 1 + 2 +… + (n - 1) = n(n - 1)/2 và số phép gán bằng 3 + 4 + .. + (n + 1) = (n +4)(n - 1)/2Tổng kết lại, ta có độ phức tạp của Insertion Sort như sau:• Trường hợp tốt nhất: O(n)• Trường hợp xấu nhất O(n2)3. Đánh giá độ phức tạp của giải thuật sắp xếp nhanh(Quick Sort)3.1. Ý tưởng thuật toán:QuickSort chia mảng thành hai danh sách bằng cách so sánh từng phần tửcủa danh sách với một phần tử được chọn được gọi là phần tử chốt. Nhữngphần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trongdanh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau vàthuộc danh sách con thứ hai. Cứ tiếp tục chia như vậy tới khi các danh sáchcon đều có độ dài bằng 1.3.2.Cài đặt thuật toán:void quicksort(int a[],int left,int right){if(left>=right)return;int x=a[(left+right)/2];int i=left;int j=right;do{while(a[i]<x)i++;while(a[j]>x)j--;if(i<=j)//chua duyet het{swap(a[i],a[j]);i++;Insertion Sort và Quick Sort Trang 3j--;}}while(i<j);quicksort(a,left,j);quicksort(a,i,right);}3.3.Độ phức tạp của thuật toánTa nhận thấy hiệu quả của thuật toán phụ thuộc vào việc chọn giá trị mốc (hay phần tử chốt).3.3.1. Trường hợp tốt nhất: mỗi lần phân hoạch ta đều chọn được phầntử median (phần tử lớn hơn hay bằng nửa số phần tử và nhỏ hơn haybằng nửa số phần tử còn lại) làm mốc. Khi đó dãy được phân hoạchthành hai phần bằng nhau, và ta cần log2(n) lần phân hoạch thì sắp xếpxong. Ta cũng dễ nhận thấy trong mỗi lần phân hoạch ta cần duyệtqua n phần tử. Vậy độ phức tạp trong trường hợp tốt nhất thuộcO(nlog2(n)).3.3.2. Trường hợp xấu nhất: mỗi lần phần hoạch ta chọn phải phần tử cógiá trị cực đại hoặc cực tiểu làm mốc. Khi đó dãy bị phân hoạch thànhhai phần không đều: một phần chỉ có một phần tử, phần còn lại có n-1phần tử. Do đó, ta cần tới n lần phân hoạch mới sắp xếp xong. Vậy độphức tạp trong trường hợp xấu nhất thuộc O(n2). Tổng kết lại, ta có độ phức tạp của Quick Sort như sau:• Trường hợp tốt nhất: O(nlog2(n))• Trường hợp xấu nhất: O(n2)• Trường hợp trung bình: O(nlog2(n))Insertion Sort và Quick Sort Trang 4PHẦN B : THỰC NGHIỆM1. Mô tả giải thuật :Giải thuật được cài đặt trên ngôn ngữ lập trình c/c++. Ý tưởng của việc càiđặt giải thuật như sau: Khởi tạo ngẫu nhiên n phần tử, ghi ra 1 file text Đọc các phần tử từ file text vào file excel Tính độ phức tạp dựa vào α2. Cài đặt2.1.InsertionSort:void insertionsort(int A1[],int num,int &sosanhI,int &hoanviI){int X=0,k=1,j=0;while(k<num){j=k+1;X=A1[j];while(X<A1[j-1]){sosanhI++;A1[j]=A1[j-1];hoanviI++;Insertion Sort và Quick Sort Trang 5

Tài liệu liên quan

• Đánh giá độ phức tạp
  • 131
  • 702
  • 3
• Đánh giá độ phúc tạp : Common_sequence
  • 22
  • 376
  • 0
• Đánh giá độ phúc tạp : complexitynotes
  • 130
  • 430
  • 0
• Đánh giá độ phúc tạp : Dynamic programming 01
  • 4
  • 494
  • 1
• Đánh giá độ phúc tạp : Giải thuật
  • 21
  • 1
  • 8
• Đánh giá độ phúc tạp : Giáo trình giải thuật
  • 109
  • 998
  • 7
• 2.Đánh giá độ phức tạp của giải thuật sắp xếp bằng phương pháp chèn(Insertion Sort)
  • 11
  • 5
  • 5
• Rèn luyện khả năng đánh giá độ phức tạp của thuật toán
  • 3
  • 1
  • 15
• Về độ phức tạp của các thuật toán số học luận văn thạc sĩ toán học
  • 51
  • 1
  • 5
• Bài giảng phân tích và thiết kế giải thuật Chương 2 : Phân tích độ phức tạp của một số giải thuật sắp thứ tự và tìm kiếm
  • 56
  • 877
  • 4

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(760.5 KB - 11 trang) - 2.Đánh giá độ phức tạp của giải thuật sắp xếp bằng phương pháp chèn(Insertion Sort) Tải bản đầy đủ ngay ×