Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 1, Phần 2: Phân tích thuật toán

1/10/2011

REVIEW

• Bài toán: Cho một tập các số nguyên S = {s1, s2, . . . , sn}, và

một giá trị đích T. Tìm một tập con của S sao cho tổng các số

trong tập con đó đúng bằng T.

Ví dụ, Tồn tại một tập con trong S = {1, 2, 5, 9, 10} mà tổng là

T = 22 nhưng lại không tồn tại với T = 23.

PHÂN TÍCH

THUẬT TOÁN

Tìm phản ví dụ cho các thuật toán sau

REVIEW

NÔI DUNG

• (a) Lần lượt chọn các phần tử trong S theo thứ tự từ trái qua

phải nếu chúng phù hợp (thuật toán first‐fit).

• Phân tích thuật toán

• Mô hình RAM

• Tốt nhất, tồi nhất, trung bình

• Ký hiệu O‐lớn

• Phân tích tiệm cận

• (b) Lần lượt chọn các phần tử trong S theo thứ tự từ nhỏ đến

lớn (thuật toán best‐fit).

• Tốc độ tăng và tính thống trị

• Một số tính chất của phân tích O‐lớn

• (c) Lần lượt chọn các phần tử trong S theo thứ tự từ lớn nhất

đến nhỏ nhất.

1

1/10/2011

PHÂN TÍCH THUẬT TOÁN?

Bài toán: tìm phần tử lớn nhất thứ k

• Đầu vào: Dãy số gồm n số nguyên ꢀ_ꢁ, ꢀ_ꢂ, . . , ꢀ_ꢃ, và số nguyên k

(0< k ≤ n)

• Đánh giá hiệu quả của thuật toán mà không cần cài đặt.

• 2 mô hình :

• Mô hình RAM (Random Access Machine)

• Phân tích tiệm cận độ phức tạp trong trường hợp tồi nhất

• Đầu ra: Giá trị phần tử lớn nhất thứ k trong dãy.

Có 2 thuật toán A, B để giải bài toán.

Với n = 100,000, k=100

• Đánh giá thuật toán: dự đoán các tài nguyên mà thuật toán

cần.

• A cài đặt bằng C chạy mất 12 s

• B cài đặt bằng java chạy mất 19 s

Thuật toán A tốt hơn B ?

• Tài nguyên: Thời gian CPU, bộ nhớ, băng thông, phần cứng…

MÔ HÌNH RAM

TỐT NHẤT, TỒI NHẤT VÀ TRUNG BÌNH

• Thực hiện thuật toán trên một máy tính giả định gọi là Random

Access Machine hoặc RAM.

• Mỗi phép tính đơn giản (+, *, –, =, if, call) thực hiện trong 1 đơn vị

thời gian (hoặc 1 bước).

• Vòng lặp, hàm, thủ tục: là kết hợp của nhiều phép tính đơn lẻ

• Mỗi bước truy cập bộ nhớ mất 1 đơn vị thời gian

• Phân tích thuật toán

trong trường hợp

tổng quát, với một

đầu vào bất kỳ thỏa

mãn

• Luôn có đủ bộ nhớ cần thiết để thực hiện thuật toán

Phân tích trường

hợp: tốt nhất, tồi nhất

và trung bình

• Đánh giá thời gian thực hiện thuật toán bằng cách đếm số đơn

vị thời gian cần.

2

1/10/2011

TỐT NHẤT, TỒI NHẤT VÀ TRUNG BÌNH

KÝ HIÊU O LỚN

• Độ phức tạp trong trường hợp tồi nhất (worst‐case complexity):

Là số lượng bước lớn nhất thuật toán cần thực hiện với bất cứ

đầu vào kích thước n nào.

• Độ phức tạp trong trường hợp tốt nhất (best‐case complexity):

Là số lượng bước nhỏ nhất thuật toán cần thực hiện với bất cứ

đầu vào kích thước n nào.

• Khó xác định chính xác các hàm đánh giá độ phức tạp trong

trường hợp tốt nhất, tồi nhất, trung bình

• Có rất nhiều điểm lồi: thời gian thực hiện biến đổi trong một số trường

hợp đầu vào đặc biệt. VD tìm kiếm nhị phân nếu đầu vào ꢆ ꢈ 2^ꢏꢋ 1

• Để chính xác thì cần phân tích rất tỉ mỉ.

ꢄꢅꢆꢇ ꢈ 120ꢆ^ꢉꢊ 12.4ꢆ^ꢂꢋ 43ꢆꢌꢍꢎꢆ ꢊ 9ꢆ

• Độ phức tạp trong trường hợp trung bình (average‐case

complexity): Là số lượng bước trung bình thuật toán cần thực

hiện trên tất cả các trường hợp đầu vào kích thước n.

• Ký hiệu O lớn: đơn giản phân tích, bỏ qua những thành phần

mà không ảnh hưởng đến khi so sánh các thuật toán

Trong phân tích O lớn ꢐ ꢆ ꢈ 2ꢆ^ꢂvà ꢎ ꢆ ꢈ 3ꢆ^ꢂꢊ 5ꢆ là tương đương

• Mỗi độ phức tạp là một hàm của thời gian và kích thước đầu vào

• Các ký hiệu tiệm cận ꢅꢑ, ꢒ, ꢓꢇ dùng để phân tích độ phức tạp

trong thực tế

ꢄꢅꢆꢇ ꢈ 120ꢆ^ꢉꢊ 12.4ꢆ^ꢂꢋ 43ꢆꢌꢍꢎꢆ ꢊ 9ꢆ

PHÂN TÍCH TIÊM CẬN

Cận trên, cận dưới để đánh giá

cho độ phức tạp của hàm

Định nghĩa O lớn chính thức:

• ꢐ ꢆ ꢈ ꢔꢅꢎꢅꢆꢇꢇ: nghĩa là ꢕ. ꢎ ꢆ là giới hạn trên của ꢐ ꢆ . Do vậy

tồn tại hằng số ꢕ sao cho ꢐ ꢆ ꢖ ꢕ. ꢎꢅꢆꢇ luôn đúng với mọi ꢆ ꢗ ꢆ_ꢘ

• ꢐ ꢆ ꢈ Ωꢅꢎꢅꢆꢇꢇ: nghĩa là ꢕ. ꢎꢅꢆꢇ là giới hạn dưới của ꢐ ꢆ . Do vậy

tồn tại hằng số ꢕ sao cho ꢐ ꢆ ꢗ ꢕ. ꢎꢅꢆꢇ luôn đúng với mọi ꢆ ꢗ ꢆ_ꢘ

• ꢐ ꢆ ꢈ Θꢅꢎꢅꢆꢇꢇ: nghĩa là ꢕ_ꢁ. ꢎꢅꢆꢇ là giới hạn trên, và ꢕ_ꢂ. ꢎꢅꢆꢇ là

giới hạn dưới của ꢐ ꢆ . Do vậy tồn tại hằng số ꢕ_ꢁvà ꢕ_ꢂsao cho

ꢐ ꢆ ꢖ ꢕ_ꢁ. ꢎꢅꢆꢇ và ꢐ ꢆ ꢗ ꢕ_ꢂ. ꢎꢅꢆꢇ luôn đúng với mọi ꢆ ꢗ ꢆ_ꢘ. Nói

cách khác ꢎꢅꢆꢇ là giới hạn chặt của ꢐꢅꢆꢇ

Với ꢕ, ꢕ_ꢁ, ꢕ_ꢂlà các hằng số dương không phụ thuộc vào ꢆ, và ꢆ_ꢘꢙ 0

Ο lớn

Ω lớn

Θ lớn

3

1/10/2011

KÝ HIÊU O LỚN

OMEGA LỚN

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢈ ꢢꢅꢛ^ꢚꢇ vì chọn ꢕ ꢈ 1.5 thì

1.5ꢆ^ꢂꢡ 2ꢆ^ꢂꢋ 4ꢆ ꢊ 5 khi ꢆ ꢙ 50

Ví dụ

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢈ ꢞꢅꢛ^ꢚꢇ vì chọn ꢕ ꢈ 2 thì 2ꢆ^ꢂꢙ 2ꢆ^ꢂꢋ 4ꢆ ꢊ 5

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢠ ꢢꢅꢛ^ꢟꢇ vì với bất kỳ giá trị ꢕ thì

cꢆ^ꢉꢙ 2ꢆ^ꢂꢋ 4ꢆ ꢊ 5 khi ꢆ đủ lớn (ꢆ ꢙ 100ꢕ nếu ꢕ ꢙ 1,

ꢆ ꢙ 10/ꢕ nếu ꢕ ꢡ 1)

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢈ ꢞꢅꢛ^ꢟꢇ vì chọn ꢕ ꢈ 1 thì ꢆ^ꢉꢙ 2ꢆ^ꢂꢋ 4ꢆ ꢊ 5 khi

ꢆ ꢙ 1

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢈ ꢢꢅꢛꢇ vì với bất kỳ hằng số c nào thì

ꢕꢆ ꢡ 2ꢆ^ꢂꢋ 4ꢆ ꢊ 5 khi ꢆ ꢙ 5ꢕ

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢠ ꢞꢅꢛꢇ vì với bất kỳ hằng số c nào thì

ꢕꢆ ꢡ 2ꢆ^ꢂꢋ 4ꢆ ꢊ 5 khi ꢆ ꢙ ꢕ

THETA LỚN

VÍ DỤ

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢈ ꢣꢅꢛ^ꢚꢇ vì cả Ο, Ω đều đúng

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢠ ꢣꢅꢛ^ꢟꢇ vì chỉ Ο đúng

• ꢚꢛ^ꢚꢋ ꢜꢛ ꢊ ꢝ ꢠ ꢣꢅꢛꢇ vì chỉ Ω đúng

Khẳng định sau đúng hay sai? Tại sao ?

• 2^ꢃꢤꢉꢈ Θꢅ2^ꢃꢇ

• 3^ꢂꢃꢈ Θꢅ3^ꢃꢇ

• ꢅꢥ ꢊ ꢦꢇ^ꢂꢈ Οꢅꢥ^ꢂꢊ ꢦ^ꢂꢇ

Để chứng minh ꢐ ꢆ ꢈ Θꢅꢎꢅꢆꢇꢇ thì cần chỉ ra

• ꢐ ꢆ ꢈ Ο ꢎ ꢆ

• ꢐ ꢆ ꢈ Ωꢅꢎꢅꢆꢇꢇ

4

1/10/2011

TỐC ĐÔ TĂNG VÀ QUAN

HÊ THỐNG TRỊ

TỐC ĐÔ TĂNG VÀ QUAN HÊ THỐNG TRỊ

• O lớn nhóm các hàm thành các lớp hàm.

ꢆ ꢊ 4 và 100.3ꢆ ꢋ 3 là thuộc lớp hàm Θ ꢆ

• Hai hàm ꢐ, ꢎ thuộc hai lớp khác nhau có quan hệ theo các ký hiệu

tiệm cận Ω, Ο khác nhau

• Tốc độ tăng của một số hàm

thông dụng

• Các lớp hàm thông dụng:

• Hàm hằng ꢐ ꢆ ꢈ 1. Thời gian thực hiện là hằng số VD hàm tính tổng 2 số

• Hàm loga ꢐ ꢆ ꢈ ꢌꢍꢎꢆ. VD tìm kiếm nhị phân

• Hàm tuyến tính ꢐ ꢆ ꢈ ꢆ. VD Tìm giá trị lớn nhất trong dãy số

• Hàm siêu tuyến tính ꢐ ꢆ ꢈ ꢆꢌꢍꢎꢆ. VD QuickSort, MergeSort

• Hàm bậc hai ꢐ ꢆ ꢈ ꢆ^ꢂ. VD Sắp xếp nổi bọt (bubble sort )

• Hàm bậc ba ꢐ ꢆ ꢈ ꢆ^ꢉ.

• Hàm mũ ꢐ ꢆ ꢈ ꢕ^ꢃ, ꢕ là hằng số >1.

• Hàm giai thừa ꢐ ꢆ ꢈ ꢆ!

TỐC ĐÔ TĂNG VÀ QUAN HÊ THỐNG TRỊ

CÁC PHÉP TÍNH VỚI O LỚN

• Quan hệ thống trị:

• Cộng hai hàm

ꢆ! ≫ ꢕ^ꢃ≫ ꢆ^ꢉ≫ ꢆ^ꢂ≫ ꢆlogꢆ ≫ ꢆ ≫ logꢆ ≫ 1

• Ο ꢐ ꢆ ꢊ Οꢅꢎꢅꢆꢇꢇ → Οꢅmax ꢐ ꢆ , ꢎꢅꢆꢇ ꢇ

• Ω ꢐ ꢆ ꢊ Ωꢅꢎꢅꢆꢇꢇ → Ωꢅmax ꢐ ꢆ , ꢎꢅꢆꢇ ꢇ

• Θ ꢐ ꢆ ꢊ Θꢅꢎꢅꢆꢇꢇ → Θꢅmax ꢐ ꢆ , ꢎꢅꢆꢇ ꢇ

• Giới hạn và quan hệ thống trị của các hàm

ꢨꢅꢃꢇ

• ꢐꢅꢆꢇ thống trị ꢎꢅꢆꢇ nếu _ꢃli_→m_ꢧ

ꢈ 0

ꢩꢅꢃꢇ

VD.

• Nhân hàm

ꢨꢅꢃꢇ

ꢩꢅꢃꢇ

ꢐ ꢆ ꢈ ꢆ^ꢂkhông thống trị ꢎ ꢆ ꢈ 3ꢆ^ꢂꢊ 5 vì _ꢃli_→m_ꢧ

ꢈ 3

• Ο ꢕ ⋅ ꢐ ꢆ → Οꢅꢐꢅꢆꢇꢇ

• Ω ꢕ ⋅ ꢐ ꢆ → Ωꢅꢐꢅꢆꢇꢇ

• Θ ꢕ ⋅ ꢐ ꢆ → Θꢅꢐꢅꢆꢇꢇ

ꢨꢅꢃꢇ

ꢐ ꢆ ꢈ ꢆ^ꢂthống trị ꢎ ꢆ ꢈ ꢆ^{ꢁ.ꢪꢪꢪꢪꢪꢪ}vì _ꢃli_→m_ꢧ

ꢈ 0

ꢩꢅꢃꢇ

ꢆ! ≫ ꢕ^ꢃ≫ ꢆ^ꢉ≫ ꢆ^ꢂ≫ ꢆ^ꢁꢤꢫ≫ ꢆlogꢆ ≫ ꢆ ≫ ꢆ ≫ log^ꢂꢆ

≫ logꢆ ≫ logꢆ/loglogꢆ ≫ loglogꢆ ≫ 1

ꢕ là một hằng số dương bất kỳ

5

1/10/2011

CÁC PHÉP TÍNH VỚI O LỚN

MỘT SỐ TÍNH CHẤT

• Nhân hai hàm

Tính truyền ứng – transitivity

• Nếu ꢐ ꢆ ꢈ Οꢅꢎꢅꢆꢇꢇ và ꢎ ꢆ ꢈ Οꢅꢬꢅꢆꢇꢇ thì ꢐ ꢆ ꢈ Οꢅꢬꢅꢆꢇꢇ

• Nếu ꢐ ꢆ ꢈ Ωꢅꢎꢅꢆꢇꢇ và ꢎ ꢆ ꢈ Ωꢅꢬꢅꢆꢇꢇ thì ꢐ ꢆ ꢈ Ωꢅꢬꢅꢆꢇꢇ

• Nếu ꢐ ꢆ ꢈ Θꢅꢎꢅꢆꢇꢇ và ꢎ ꢆ ꢈ Θꢅꢬꢅꢆꢇꢇ thì ꢐ ꢆ ꢈ Θꢅꢬꢅꢆꢇꢇ

• Ο ꢐ ꢆ ∗ Οꢅꢎꢅꢆꢇꢇ → Οꢅꢐ ꢆ ∗ ꢎꢅꢆꢇꢇ

• Ω ꢐ ꢆ ∗ Ωꢅꢎꢅꢆꢇꢇ → Ωꢅꢐ ꢆ ∗ ꢎꢅꢆꢇꢇ

• Θ ꢐ ꢆ ∗ Θꢅꢎꢅꢆꢇꢇ → Θꢅꢐ ꢆ ∗ ꢎꢅꢆꢇꢇ

Tính đối xứng – symmetry

• ꢐ ꢆ ꢈ Θꢅꢎꢅꢆꢇꢇ khi và chỉ khi ꢎꢅꢆꢇ ꢈ Θꢅꢐꢅꢆꢇꢇ

Tính đối xứng chuyển vị ‐ transpose symmetry

• ꢐ ꢆ ꢈ Οꢅꢎꢅꢆꢇꢇ khi và chỉ khi ꢎ ꢆ ꢈ Ωꢅꢐꢅꢆꢇꢇ

MỘT SỐ TÍNH CHẤT

MỘT SỐ VÍ DỤ

Thuật toán sắp xếp lựa chọn – Selection Sort

Chứng minh

Nếu ꢐ ꢆ ꢈ Οꢅꢎꢅꢆꢇꢇ và ꢎ ꢆ ꢈ Οꢅꢬꢅꢆꢇꢇ thì ꢐ ꢆ ꢈ Οꢅꢬꢅꢆꢇꢇ

selection_sort(int s[], int n)

{

Ta có

int i,j; /* counters */

int min; /* index of minimum */

for (i=0; i<n; i++) {

min=i;

for (j=i+1; j<n; j++)

if (s[j] < s[min]) min=j;

swap(&s[i],&s[min]);

}

• ꢐ ꢆ ꢈ Οꢅꢎꢅꢆꢇꢇ tức là ꢐꢅꢆꢇ ꢖ ꢕ_ꢁꢎꢅꢆꢇ với ꢆ ꢙ ꢆ_ꢁ

• ꢎ ꢆ ꢈ Οꢅꢬꢅꢆꢇꢇ tức là ꢎꢅꢆꢇ ꢖ ꢕ_ꢂꢬꢅꢆꢇ với ꢆ ꢙ ꢆ_ꢂ

Suy ra

• ꢐꢅꢆꢇ ꢖ ꢕ_ꢁꢎꢅꢆꢇ ꢖ ꢕ_ꢁꢕ_ꢂꢬꢅꢆꢇ với ꢆ ꢙ maxꢅꢆ_ꢁ, ꢆ_ꢂꢇ

Chọn ꢕ_ꢉꢈ ꢕ_ꢁꢕ_ꢂvà ꢆ_ꢉꢈ maxꢅꢆ_ꢁ, ꢆ_ꢂꢇ thì ꢐꢅꢆꢇ ꢖ ꢕ_ꢉꢬ ꢆ khi ꢆ ꢙ ꢆ_ꢉ

Vậy ꢐ ꢆ ꢈ Οꢅꢬꢅꢆꢇꢇ

}

6

1/10/2011

MỘT SỐ VÍ DỤ

• Lệnh được lặp lại nhiều nhất chính là lệnh if

• Phân tích chi tiết hơn

• ꢮ ꢈ 0 lệnh if lặp ꢆ ꢋ 2 lần (từ 1 tới n‐1)

• ꢮ ꢈ 1 lệnh if lặp ꢆ ꢋ 3 lần (từ 2 tới n‐1)

…

Phân tích trong trường hợp tồi nhất

• Vòng lặp ngoài lặp n lần (từ 0 tới n‐1)

• ꢮ ꢈ ꢆ ꢋ 2 lệnh if lặp 1 lần (từ n‐1 tới n‐1)

• ꢮ ꢈ ꢆ ꢋ 1 lệnh if lặp 0 lần

• Vòng lặp trong lặp n lần ứng với mỗi lần lặp của vòng ngoài

• Số lần lặp của if sẽ là

• Vậy số lượng bước (thời gian) cần thực hiện trong trường

hợp tồi nhất là ꢆ ꢭ ꢆ → Οꢅꢆ^ꢂꢇ

ꢄ ꢆ ꢈ ꢆ ꢋ 2 ꢊ ꢆ ꢋ 3 ꢊ ⋯ ꢊ 1 ꢊ 0 ꢈ ꢅꢆ ꢋ 2ꢇꢅꢆ ꢋ 1ꢇ/2

• Vậy ꢄ ꢆ ꢈ Θꢅꢆ^ꢂꢇ

MỘT SỐ VÍ DỤ

• Sắp xếp chèn – Insertion Sort

for (i=1; i<n; i++) {

• Phân tích trong trường hợp tồi nhất

• ꢮ ꢈ 1 lệnh cơ sở lặp 1 lần

• ꢮ ꢈ 2 lệnh cơ sở lặp 2 lần

…

j=i;

while ((j>0) && (s[j] < s[j‐1])) {

swap(&s[j],&s[j‐1]);

• ꢮ ꢈ ꢆ ꢋ 2 lệnh cơ sở lặp ꢆ ꢋ 2 lần

• ꢮ ꢈ ꢆ ꢋ 1 lệnh cơ sở lặp ꢆ ꢋ 1 lần

j = j‐1;

}

• Số lần lặp của lệnh cơ sở sẽ là

ꢄ ꢆ ꢈ 1 ꢊ 2 ꢊ ⋯ ꢊ ꢆ ꢋ 2 ꢊ ꢆ ꢋ 1 ꢈ ꢆ ꢋ 1 ꢆ/2

• Vậy ꢄ ꢆ ꢈ Οꢅꢆ^ꢂꢇ

• Lệnh được lặp nhiều nhất là 2 lệnh bên trong while : lệnh cơ sở

7

1/10/2011

Môt số công thức hay dùng

^ꢯ_ꢰ1 ꢈ ꢱ ꢋ ꢀ ꢊ 1

∑

•

ꢃ

∑

•

_ꢲꢳꢁꢮ ꢈ 1 ꢊ 2ꢊ. . ꢊꢆ ꢈ ^{ꢃ ꢃꢤꢁ}

ꢂ

ꢷ

ꢃ ꢤꢃꢶꢲ ꢤꢲ

ꢴ ꢈ

ꢂ

ꢃ

ꢲꢶꢁ

ꢵꢳꢁ

∑

_ꢵꢳꢲꢴ ꢈ ꢮ ꢊ ꢮ ꢊ 1 ꢊ. . ꢊꢆ ꢈ _ꢲꢳꢁꢮ ꢋ

ꢸ

ꢷ

ꢂꢃ ꢤꢉꢃ ꢤꢃ

ꢹ

ꢃ

ꢂ

_ꢲꢳꢁꢮ ꢈ 1^ꢂꢊ 2^ꢂꢊ 3^ꢂꢊ. . ꢊꢆ^ꢂꢈ

ꢺꢻꢼ

ꢰ

ꢶꢁ

• ꢀ^ꢘꢊ ꢀ^ꢁꢊ. . ꢊꢀ^ꢃ

ꢈ

với ꢀ ꢠ 1

ꢰꢶꢁ

ꢁ

ꢧ

ꢲ

∑

•

_ꢲꢳꢘꢥ ꢈ _ꢁꢶꢽnếu ꢥ ꢡ 1

ꢺꢻꢼ

ꢾꢶꢁ

ꢺ

ꢃꢶꢁ ꢾ

ꢶꢃꢾ ꢤꢾ

ꢃ

_ꢲꢳꢁꢮꢕ^ꢲꢈ ꢕ ꢊ 2ꢕ^ꢂꢊ. . ꢊꢆꢕ^ꢃ

ꢈ

ꢷ

8

Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 1, Phần 2: Phân tích thuật toán - Nguyễn Duy Hiệp