Độ phức tạp của thuật toán quicksort

     

Quý Khách sẽ coi bạn dạng rút gọn của tư liệu. Xem và tải tức thì bạn dạng tương đối đầy đủ của tài liệu tại phía trên (633.01 KB, 12 trang )


Bạn đang xem: Độ phức tạp của thuật toán quicksort

Luận vănSo sánh độ phức tạp của thuật toán QuickSort và InsertSortInsertion Sort cùng Quichồng Sort Trang 1PHẦN A: NỀN TẢNG LÝ THUYẾT1. Mô tả chức năng với yêu thương cầu1.1.Khái quát tháo về sắp xếp:Để dễ dàng và giảm tphát âm thời hạn thao tác mà đặc biệt là để tra cứu kiếm tài liệu tiện lợi và mau lẹ,thong hay trước khi thao tác làm việc thì dữ liệu trên mảng,bên trên tập tin đang tất cả trang bị từ.Do vậy làm việc sắp xếp tài liệu là một Một trong những thao tác cần thiết với hay gặp gỡ vào quá trình tàng trữ,thống trị dữ liệuCó không hề ít biện pháp sắp xếp tài liệu,tuy vậy ở chỗ này ta chỉ quan tâm cho 2 thuật toán thù là sắp xếp bởi phương thức chèn (Insertion Sort) cùng sắp xếp dựa trên sự phân hoạch (Quichồng Sort).Ta vẫn đi đối chiếu nhị thuật toán bố trí này để so sánh và Review độ phức tạp của chúng.1.2.Mục tiêu của bài toán:Phân tích,Review và đối chiếu độ phức tạp(bên trên lý thuyết) với đối chiếu thời gian tính toán(bên trên thực nghiệm) của 2 lời giải.2. Đánh giá chỉ độ phức tạp của giải mã sắp xếp bằng phương thức chèn(Insertion Sort)2.1.Ý tưởng thuật toán:Giả sử ta tất cả hàng a1, a2, …, an trong đó i thành phần trước tiên a1, a
2, …, ai đó đã bao gồm sản phẩm công nghệ từ bỏ. Ý tưởng của thuật toán thù là search vị trị phù hợp và chèn phần tử ai+1 vào hàng đang bao gồm vật dụng tự bên trên để sở hữu được một dãy new bao gồm thứ trường đoản cú. Cứ đọng cầm, làm mang đến cuối hàng ta sẽ tiến hành một dãy tất cả vật dụng tự.Với hàng lúc đầu a1, a2, …, an ta có thể coi đoạn chỉ bao gồm một trong những phần tử a1 là một quãng đã gồm thứ trường đoản cú, tiếp đến ta cyếu phần tử a2 vào dãy a1 để sở hữu hàng a1a2 gồm trang bị trường đoản cú. Tiếp đó, ta lại ckém bộ phận a3 vào dãy a
1a2 để có hàng a1a2a3 gồm máy trường đoản cú. Cứ đọng cố gắng, cho cuối cùng ta cnhát thành phần an vào hàng a1a2…an-1 ta sẽ được hàng a1a2…an có thiết bị từ bỏ.Insertion Sort cùng Quiông chồng Sort Trang 22.2.Cài đặt thuật toánvoid insertionsort(int a<>,int n)
int pos,x;for(int i=0;ix=a;pos=i;while(pos>=0 && a>x)a=a;pos ;a=x;2.3.Đánh giá bán độ phức tạp:Ta thấy những phép so sánh xảy ra trong vòng lặp nhằm tìm kiếm địa điểm tương thích pos để cnhát x. Mỗi lần đối chiếu nhưng mà thấy vị trí sẽ xét không tương thích, ta dời bộ phận a thanh lịch yêu cầu.Ta cũng thấy số phxay gán cùng số phnghiền so sánh của thuật toán thù phụ thuộc vào vào triệu chứng của dãy thuở đầu. Do đó ta chỉ rất có thể ước chừng nlỗi sau:2.3.1. Trường đúng theo xuất sắc nhất: Dãy ban đầu vẫn bao gồm lắp thêm tự. Ta tìm được ngay vị trí phù hợp để chèn ngay lần đối chiếu thứ nhất cơ mà không nhất thiết phải vô vòng lặp. Vậy nên, với i chạy từ 2 mang đến n thì số phnghiền so sánh tổng cộng đã là n-1. Còn với số phnghiền gán, vì thuật toán ko chạy vào vòng lặp buộc phải xét i ngẫu nhiên, ta luôn chỉ bắt buộc tốn 2 phxay gán(x = a cùng a = x). Từ trên đây, ta tính được số phép gán tổng cộng bởi 2(n - 1).2.3.2. Trường hợp xấu nhất:Dãy ban sơ gồm vật dụng từ bỏ ngược. Ta thấy ngay lập tức vị trí thích hợp pos luôn luôn là vị trí thứ nhất của hàng sẽ gồm sản phẩm công nghệ từ bỏ, với vị Insertion Sort với Quichồng Sort Trang 3đó, nhằm đưa ra địa điểm này ta nên chú tâm hết dãy sẽ gồm sản phẩm công nghệ từ. Xét i bất kỳ, ta có số phnghiền đối chiếu là i-1, số phép gán là (i - 1) + 2 = i + 1. Với i chạy từ 2 đến n, ta tính được số phxay so sánh tổng số bởi 1 + 2 +
… + (n - 1) = n(n - 1)/2 cùng số phép gán bởi 3 + 4 + + (n + 1) = (n + 4)(n - 1)/2Tổng đặc lại, ta gồm độ tinh vi của Insertion Sort như sau:• Trường hòa hợp giỏi nhất: O(n)• Trường hợp xấu độc nhất vô nhị O(n2)3. Đánh giá độ phức tạp của giải thuật sắp xếp nhanh(Quiông chồng Sort)3.1.Ý tưởng thuật toán:QuickSort phân chia mảng thành nhì list bằng cách đối chiếu từng thành phần của list với một trong những phần tử được lựa chọn được Hotline là bộ phận chốt. Những thành phần bé dại hơn hoặc bởi thành phần chốt được đưa về phía trước cùng phía trong danh sách nhỏ thứ nhất, các thành phần lớn hơn chốt được đưa về vùng phía đằng sau với trực thuộc list con vật dụng nhì. Cứ liên tiếp phân tách như vậy cho tới Lúc các list con đều phải có độ nhiều năm bởi 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;dowhile(awhile(a>x)j ;if(iswap(a,a);i++;
Insertion Sort và Quick Sort Trang 4j ;while(iquicksort(a,left,j);quicksort(a,i,right);3.3.Độ tinh vi của thuật toánTa nhận thấy công dụng của thuật toán thù dựa vào vào câu hỏi chọn giá trị mốc (tuyệt bộ phận chốt).3.3.1. Trường phù hợp giỏi nhất: mỗi lần phân hoạch ta đa số chọn được bộ phận median (thành phần lớn hơn hay bằng nửa số bộ phận và bé dại hơn giỏi bằng nửa số thành phần còn lại) có tác dụng mốc. Khi kia hàng được phân hoạch thành nhị phần bằng nhau, cùng ta đề xuất log2(n) lần phân hoạch thì thu xếp chấm dứt. Ta cũng dễ phân biệt trong mỗi lần phân hoạch ta cần chu đáo qua n phần tử. Vậy độ tinh vi vào trường hợp tốt nhất có thể trực thuộc O(nlog2(n)).3.3.2. Trường đúng theo xấu nhất: các lần phần hoạch ta lựa chọn nên thành phần có giá trị cực lớn hoặc rất tè làm cho mốc. Lúc kia dãy bị phân hoạch thành nhì phần không đều: một trong những phần chỉ tất cả 1 phần tử, phần sót lại tất cả n-một phần tử. Do đó, ta phải tới n lần phân hoạch new bố trí ngừng. Vậy độ phức tạp vào ngôi trường hợp xấu độc nhất vô nhị ở trong O(n2). Tổng đặc lại, ta tất cả độ phức tạp của Quichồng Sort như sau:• Trường hòa hợp xuất sắc nhất: O(nlog

Xem thêm: Học Ngay Các Kiểu Tóc Của Rose(Blackpink), Chưa Kịp Làm Tóc Tết Đã Đến

2(n))• Trường đúng theo xấu nhất: O(n2)• Trường hòa hợp trung bình: O(nlog2(n))Insertion Sort cùng Quiông chồng Sort Trang 5PHẦN B : THỰC NGHIỆM1. Mô tả giải thuật :Giải thuật được download để trên ngôn từ lập trình sẵn c/c++. Ý tưởng của vấn đề càiđặt giải mã như sau: Khởi tạo ra tình cờ n thành phần, ghi ra 1 file autotruyenky.vn Đọc các bộ phận từ tệp tin autotruyenky.vn vào file excel Tính độ phức hợp phụ thuộc α2. Cài đặt2.1.InsertionSort:void insertionsort(int A1<>,int num,int &sosanhI,int &hoanviI)int X=0,k=1,j=0;while(kj=k+1;X=A1;while(XsosanhI++;A1=A1;hoanviI++;
Insertion Sort và Quichồng Sort Trang 6j ;A1=X;k++;2.2.QuickSortvoid quicksort(int A2<>,int first,int last,int &sosanhQ,int &hoanviQ)if(first>=last)return;int mid=(first+last)/2;int MID=A2;int F=first,L=last;while(Fwhile(A2F++;sosanhQ++;while(A2>MID)L ;if(Fdoicho(A2,A2);F++;L ;hoanviQ++;
cout.flush();quicksort(A2,first,L,sosanhQ,hoanviQ);cout.flush();Insertion Sort với Quick Sort Trang 7quicksort(A2,F,last,sosanhQ,hoanviQ);3. Kết quả tình nghiệm:Bảng số liệu nhận được lúc lịch trình chạyInsertion Sort cùng Quichồng Sort Trang 8Insertion Sort cùng Quiông chồng Sort Trang 9Insertion Sort và Quiông xã Sort Trang 10Insertion Sort và Quick Sort Trang 11KẾT LUẬNDựa vào phương thơm trình hồi qui đường tính của Phxay Hoán thù vị(Gán) InsertionSort với phương trình hồi qui con đường tính Phxay Hoán thù vị(Gán) QuickSort ; phương trình hồi qui tuyến tính của Phép So sánh InsertionSort với phương trình hồi qui tuyến tính Phép So Sánh QuickSort,ta thấy thông số α của giải thuật QuickSort nhỏ dại hơn thông số α của lời giải InsertionSort,điều đó chứng tỏ giải mã QuickSort chạy nhanh hơn giải mã InsertSort.Hình như,vật thị màn biểu diễn các phương trình hồi qui đường tính của 2 giải mã cũng cho biết rằng lời giải QuickSort chạy nkhô giòn rộng giải thuật InsertionSort.Phần lý thuyết cũng cho biết độ phức hợp của lời giải InsertionSort lớn hơn hoặc bằng độ phức hợp của giải thuật QuickSort.Nhóm chúng em vẫn nỗ lực tìm hiểu thâm thúy hơn để hiểu rõ về nhì lời giải này,trong quá trình làm không tránh khỏi thiếu hụt xót,kính ao ước Thầy bỏ qua.Xin chân thành cảm ơn.Insertion Sort cùng Quiông xã Sort Trang 12

Tài liệu liên quan


*
Phân tích độ phức tạp của 1 số giải thuật sắp tới thứ tự cùng tìm kiếm kiếm 56 1 8
*
Đánh giá chỉ độ phúc tạp : Giải thuật 21 879 6
*
So sánh độ liền lạc của sườn Zirconia mang lại mão toàn sứ đọng với sườn sắt kẽm kim loại cho mão sứ đọng kim loại 17 622 0