Đá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

Bạn đang xem bản đúc kết của ebook. Xem & tải ngay bản đầy đủ của ebook tại đây (633.01 KB, 12 trang )

2.2.Seting thuật toán

void insertionsort(int α[],int ռ)

{

int pos,Ҳ;

for(int ι=0;ι
{

Ҳ=α[i+1];pos=ι;

while(posvàgt;=0 && α[pos]>Ҳ)

{

α[pos+1]=α[pos];

pos–;

}

α[pos+1]=Ҳ;

}

}

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 địa điểm phù hợp pos

để chèn Ҳ. Mỗi lần so sánh mà thấy địa điểm đang xét không phù hợp, ta dời phần

tử α[pos] sang phải.

Ta cũng thấy số phép gán & số phép so sánh của thuật toán lệ thuộc vào

hiện trạng của dãy ban đầu. Vì vậy 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 ngay

địa điểm phù hợp để chèn ngay lần so sánh trước nhất mà không cần phải

vô vòng lặp. Như thế, với ι chạy từ 2 đến ռ thì số phép so sánh tổng

cộng sẽ là n-1. Còn với số phép gán, do thuật toán không chạy vào

vòng lặp nên xét ι bất kỳ, ta luôn chỉ phải tốn 2 phép gán(Ҳ = α[i] &

α[pos] = Ҳ). Từ đây, ta tính được số phép gán tổng cộng bằng 2(ռ – 1).

2.3.2. Trường hợp xấu nhất:Dãy ban đầu có thứ tự ngược. Ta thấy ngay

địa điểm phù hợp pos luôn là hàng đầu của dãy đã có thứ tự, & do

Insertion Sort & Quick Sort

Trang 3

đó, để tìm thấy địa điểm này ta phải duyệt hết dãy đã có thứ tự. Xét ι bất kỳ,

Xem Thêm  : Phần tử Đầu vào (Đầu vào biểu mẫu) - HTML: Ngôn ngữ đánh dấu siêu văn bản - nhập thẻ trong html

ta có số phép so sánh là i-1, số phép gán là (ι – 1) + 2 = ι + 1. Với ι

chạy từ 2 đến ռ, ta tính được số phép so sánh tổng cộng bằng 1 + 2 +

… + (ռ – 1) = ռ(ռ – 1)/2 & số phép gán bằng 3 + 4 + .. + (ռ + 1) = (ռ +

4)(ռ – 1)/2

Kết luận lại, ta có độ phức tạp của Insertion Sort như sau:

• Trường hợp tốt nhất: Σ(ռ)

• Trường hợp xấu nhất Σ(n2)

3.

Đánh giá độ phức tạp của giải thuật sắp xếp nhanh(Quick Sort)

3.1.Sáng kiến thuật toán:

QuickSort chia mảng thành hai mục lục bằng cách so sánh từng phần tử

của mục lục với một phần tử được chọn được gọi là phần tử chốt. Những

phần tử bé hơn hoặc bằng phần tử chốt được mang về phía trước & nằm trong

mục lục con đầu tiên, các phần tử to hơn chốt được mang về phía sau &

thuộc mục lục con thứ hai. Cứ tiếp tục chia như thế tới khi các mục lục

con đều có độ dài bằng 1.

3.2.Seting thuật toán:

void quicksort(int α[],int left,int right)

{

if(leftvàgt;=right)return;

int Ҳ=α[(left+right)/2];

int ι=left;

int j=right;

do

{

while(α[i]
while(α[j]>Ҳ)j–;

if(ivàlt;=j)//chua duyet het

{

swap(α[i],α[j]);

ι++;

Insertion Sort & Quick Sort

Trang 4

j–;

}

}while(ι
quicksort(α,left,j);

quicksort(α,ι,right);

}

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

Ta nhận biết hiệu quả của thuật toán lệ 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ần

Xem Thêm  Hơn 10 ví dụ đơn giản để học python, hãy thử ngoại trừ chi tiết - thử và ngoại trừ trong các ví dụ về python

tử median (phần tử to hơn hay bằng nửa số phần tử & bé hơn hay

bằng nửa số phần tử còn sót lại) làm mốc. Khi đó dãy được phân hoạch

thành hai phần bằng nhau, & ta cần log2(ռ) lần phân hoạch thì sắp xếp

xong. Ta cũng dễ nhận biết trong mỗi lần phân hoạch ta cần duyệt

qua ռ phần tử. Vậy độ phức tạp trong trường hợp tốt nhất thuộc

Σ(nlog2(ռ)).

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ành

hai phần không đều: một phần chỉ có một phần tử, phần còn sót lại có n-1

phần tử. Vì vậy, ta cần tới ռ 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 Σ(n2).

Kết luận lại, ta có độ phức tạp của Quick Sort như sau:

• Trường hợp tốt nhất: Σ(nlog2(ռ))

• Trường hợp xấu nhất: Σ(n2)

• Trường hợp bình quân: Σ(nlog2(ռ))

Insertion Sort & Quick Sort

Trang 5

PHẦN Ɓ : THỰC NGHIỆM

1.

Miêu tả giải thuật :

Giải thuật được seting trên từ ngữ lập trình ͼ/ͼ++. Sáng kiến của việc cài

đặt giải thuật như sau:

Khởi tạo đột nhiê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 trên a

2.

Seting

2.1.InsertionSort:

void insertionsort(int A1[],int num,int &sosanhI,int &hoanviI)

{

int Ҳ=0,ƙ=1,j=0;

while(ƙ
{

Xem Thêm  Ví dụ về lớp Python - các lớp trong ví dụ python

j=ƙ+1;

Ҳ=A1[j];

while(Ҳ
{

sosanhI++;

A1[j]=A1[j-1];

hoanviI++;

Insertion Sort & Quick Sort

Trang 6

j–;

}

A1[j]=Ҳ;

ƙ++;

}

}

2.2.QuickSort

void quicksort(int A2[],int first,int last,int &sosanhQ,int &hoanviQ)

{

if(firstvàgt;=last)

return;

int mid=(first+last)/2;

int MID=A2[mid];

int ₣=first,ɭ=last;

while(Fvàlt;=ɭ)

{

while(A2[F]
{

₣++;

sosanhQ++;

}

while(A2[L]>MID)

ɭ–;

if(Fvàlt;=ɭ)

{

doicho(A2[F],A2[L]);

₣++;

ɭ–;

hoanviQ++;

}

}

cout.flush();

quicksort(A2,first,ɭ,sosanhQ,hoanviQ);

cout.flush();

Insertion Sort & Quick Sort

Trang 7

quicksort(A2,₣,last,sosanhQ,hoanviQ);

}

3.

Kết quả thí nghiệm:

Bảng số liệu nhận được khi chương trình chạy

Insertion Sort & Quick Sort

Trang 8

Insertion Sort & Quick Sort

Trang 9

Insertion Sort & Quick Sort

Trang 10

Insertion Sort & Quick Sort

Trang 11

KẾT LUẬN

Dựa trên phương trình hồi qui tuyến tính của Phép Hoán vị(Gán)

InsertionSort & phương trình hồi qui tuyến tính Phép Hoán vị(Gán) QuickSort ;

phương trình hồi qui tuyến tính của Phép So sánh InsertionSort & phương trình

hồi qui tuyến tính Phép So Sánh QuickSort,ta thấy hệ số a của giải thuật

QuickSort bé hơn hệ số a của giải thuật InsertionSort,điều này chứng tỏ giải

thuật QuickSort chạy mau hơn giải thuật InsertSort.không dừng lại ở đó,đồ thị trình diễn

các phương trình hồi qui tuyến tính của 2 giải thuật cũng cho thấy rằng giải thuật

QuickSort chạy mau hơn giải thuật InsertionSort.

Phần lý thuyết cũng cho thấy độ phức tạp của giải thuật InsertionSort lớn

hơn hoặc bằng độ phức tạp của giải thuật QuickSort.

Nhóm chúng em sẽ nỗ lực khám phá sâu sắc hơn để thấu hiểu về hai giải

thuật này,trong tiến trình làm không tránh khỏi thiếu xót,kính mong Thầy bỏ qua.

Xin chân tình cảm ơn.

Insertion Sort & Quick Sort

Trang 12

Viết một bình luận