Bài giảng Cấu trúc dữ liệu và giải thuật: 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).

• (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).

• (c) Lần lượt chọn các phần tử trong S theo thứ tự từ lớn nhất • 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 • 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 đến nhỏ nhất.

1/10/2011

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

• Đánh giá hiệu quả của thuật toán mà không cần cài đặt. • 2 mô hình : 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 (cid:1853)(cid:2869), (cid:1853)(cid:2870), . . , (cid:1853)(cid:3041), và số nguyên k (0< k ≤ n) • Đầu ra: Giá trị phần tử lớn nhất thứ k trong dãy. • 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

• Đánh giá thuật toán: dự đoán các tài nguyên mà thuật toán cần. • Tài nguyên: Thời gian CPU, bộ nhớ, băng thông, phần cứng…

Có 2 thuật toán A, B để giải bài toán. Với n = 100,000, k=100 • 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 ?

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

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

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

• 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 • Luôn có đủ bộ nhớ cần thiết để thực hiện thuật toán

• 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

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.

1/10/2011

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

KÝ HIÊU O LỚN

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

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

(cid:1846)(cid:4666)(cid:1866)(cid:4667) (cid:3404) 120(cid:1866)(cid:2871) (cid:3397) 12.4(cid:1866)(cid:2870) (cid:3398) 43(cid:1866)(cid:1864)(cid:1867)(cid:1859)(cid:1866) (cid:3397) 9(cid:1866)

• Độ 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. 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 (cid:1866) (cid:3404) 2(cid:3038) (cid:3398) 1

• Độ 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. • Độ phức tạp trong trường hợp trung bình (average‐case • Ký hiệu O lớn: đơn giản phân tích, bỏ qua những thành phần

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. 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 (cid:1858) (cid:1866) (cid:3404) 2(cid:1866)(cid:2870) và (cid:1859) (cid:1866) (cid:3404) 3(cid:1866)(cid:2870) (cid:3397) 5(cid:1866) là tương đương

(cid:1846)(cid:4666)(cid:1866)(cid:4667) (cid:3404) 120(cid:1866)(cid:2871) (cid:3397) 12.4(cid:1866)(cid:2870) (cid:3398) 43(cid:1866)(cid:1864)(cid:1867)(cid:1859)(cid:1866) (cid:3397) 9(cid:1866)

• 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 (cid:4666)(cid:1997), (cid:1990), (cid:2007)(cid:4667) dùng để phân tích độ phức tạp trong thực tế

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: • (cid:1858) (cid:1866) (cid:3404) (cid:1841)(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667): nghĩa là (cid:1855). (cid:1859) (cid:1866) là giới hạn trên của (cid:1858) (cid:1866) . Do vậy tồn tại hằng số (cid:1855) sao cho (cid:1858) (cid:1866) (cid:3409) (cid:1855). (cid:1859)(cid:4666)(cid:1866)(cid:4667) luôn đúng với mọi (cid:1866) (cid:3410) (cid:1866)(cid:2868) • (cid:1858) (cid:1866) (cid:3404) Ω(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667): nghĩa là (cid:1855). (cid:1859)(cid:4666)(cid:1866)(cid:4667) là giới hạn dưới của (cid:1858) (cid:1866) . Do vậy tồn tại hằng số (cid:1855) sao cho (cid:1858) (cid:1866) (cid:3410) (cid:1855). (cid:1859)(cid:4666)(cid:1866)(cid:4667) luôn đúng với mọi (cid:1866) (cid:3410) (cid:1866)(cid:2868)

• (cid:1858) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667): nghĩa là (cid:1855)(cid:2869). (cid:1859)(cid:4666)(cid:1866)(cid:4667) là giới hạn trên, và (cid:1855)(cid:2870). (cid:1859)(cid:4666)(cid:1866)(cid:4667) là giới hạn dưới của (cid:1858) (cid:1866) . Do vậy tồn tại hằng số (cid:1855)(cid:2869) và (cid:1855)(cid:2870) sao cho (cid:1858) (cid:1866) (cid:3409) (cid:1855)(cid:2869). (cid:1859)(cid:4666)(cid:1866)(cid:4667) và (cid:1858) (cid:1866) (cid:3410) (cid:1855)(cid:2870). (cid:1859)(cid:4666)(cid:1866)(cid:4667) luôn đúng với mọi (cid:1866) (cid:3410) (cid:1866)(cid:2868). Nói cách khác (cid:1859)(cid:4666)(cid:1866)(cid:4667) là giới hạn chặt của (cid:1858)(cid:4666)(cid:1866)(cid:4667)

Ο lớn

Ω lớn

Θ lớn

Với (cid:1855), (cid:1855)(cid:2869), (cid:1855)(cid:2870) là các hằng số dương không phụ thuộc vào (cid:1866), và (cid:1866)(cid:2868) (cid:3408) 0

1/10/2011

KÝ HIÊU O LỚN

OMEGA LỚN

Ví dụ • (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3404) (cid:2233)(cid:4666)(cid:2196)(cid:2779)(cid:4667) vì chọn (cid:1855) (cid:3404) 1.5 thì 1.5(cid:1866)(cid:2870) (cid:3407) 2(cid:1866)(cid:2870) (cid:3398) 4(cid:1866) (cid:3397) 5 khi (cid:1866) (cid:3408) 50

• (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3404) (cid:2171)(cid:4666)(cid:2196)(cid:2779)(cid:4667) vì chọn (cid:1855) (cid:3404) 2 thì 2(cid:1866)(cid:2870) (cid:3408) 2(cid:1866)(cid:2870) (cid:3398) 4(cid:1866) (cid:3397) 5 • (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3405) (cid:2233)(cid:4666)(cid:2196)(cid:2780)(cid:4667) vì với bất kỳ giá trị (cid:1855) thì

• (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3404) (cid:2171)(cid:4666)(cid:2196)(cid:2780)(cid:4667) vì chọn (cid:1855) (cid:3404) 1 thì (cid:1866)(cid:2871) (cid:3408) 2(cid:1866)(cid:2870) (cid:3398) 4(cid:1866) (cid:3397) 5 khi c(cid:1866)(cid:2871) (cid:3408) 2(cid:1866)(cid:2870) (cid:3398) 4(cid:1866) (cid:3397) 5 khi (cid:1866) đủ lớn ((cid:1866) (cid:3408) 100(cid:1855) nếu (cid:1855) (cid:3408) 1, (cid:1866) (cid:3408) 10/(cid:1855) nếu (cid:1855) (cid:3407) 1) (cid:1866) (cid:3408) 1

• (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3404) (cid:2233)(cid:4666)(cid:2196)(cid:4667) vì với bất kỳ hằng số c nào thì • (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3405) (cid:2171)(cid:4666)(cid:2196)(cid:4667) vì với bất kỳ hằng số c nào thì (cid:1855)(cid:1866) (cid:3407) 2(cid:1866)(cid:2870) (cid:3398) 4(cid:1866) (cid:3397) 5 khi (cid:1866) (cid:3408) 5(cid:1855) (cid:1855)(cid:1866) (cid:3407) 2(cid:1866)(cid:2870) (cid:3398) 4(cid:1866) (cid:3397) 5 khi (cid:1866) (cid:3408) (cid:1855)

THETA LỚN

VÍ DỤ

Khẳng định sau đúng hay sai? Tại sao ? • (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3404) (cid:2726)(cid:4666)(cid:2196)(cid:2779)(cid:4667) vì cả Ο, Ω đều đúng

• 2(cid:3041)(cid:2878)(cid:2871) (cid:3404) Θ(cid:4666)2(cid:3041)(cid:4667) • (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3405) (cid:2726)(cid:4666)(cid:2196)(cid:2780)(cid:4667) vì chỉ Ο đúng

• 3(cid:2870)(cid:3041) (cid:3404) Θ(cid:4666)3(cid:3041)(cid:4667) • (cid:2779)(cid:2196)(cid:2779) (cid:3398) (cid:2781)(cid:2196) (cid:3397) (cid:2782) (cid:3405) (cid:2726)(cid:4666)(cid:2196)(cid:4667) vì chỉ Ω đúng

• (cid:4666)(cid:1876) (cid:3397) (cid:1877)(cid:4667)(cid:2870)(cid:3404) Ο(cid:4666)(cid:1876)(cid:2870) (cid:3397) (cid:1877)(cid:2870)(cid:4667) Để chứng minh (cid:1858) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) thì cần chỉ ra

• (cid:1858) (cid:1866) (cid:3404) Ο (cid:1859) (cid:1866) • (cid:1858) (cid:1866) (cid:3404) Ω(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

1/10/2011

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. (cid:1866) (cid:3397) 4 và 100.3(cid:1866) (cid:3398) 3 là thuộc lớp hàm Θ (cid:1866) • Tốc độ tăng của một số hàm • Hai hàm (cid:1858), (cid:1859) thuộc hai lớp khác nhau có quan hệ theo các ký hiệu thông dụng

• Hàm hằng (cid:1858) (cid:1866) (cid:3404) 1. Thời gian thực hiện là hằng số VD hàm tính tổng 2 số • Hàm loga (cid:1858) (cid:1866) (cid:3404) (cid:1864)(cid:1867)(cid:1859)(cid:1866). VD tìm kiếm nhị phân • Hàm tuyến tính (cid:1858) (cid:1866) (cid:3404) (cid:1866). VD Tìm giá trị lớn nhất trong dãy số • Hàm siêu tuyến tính (cid:1858) (cid:1866) (cid:3404) (cid:1866)(cid:1864)(cid:1867)(cid:1859)(cid:1866). VD QuickSort, MergeSort • Hàm bậc hai (cid:1858) (cid:1866) (cid:3404) (cid:1866)(cid:2870). VD Sắp xếp nổi bọt (bubble sort ) • Hàm bậc ba (cid:1858) (cid:1866) (cid:3404) (cid:1866)(cid:2871). • Hàm mũ (cid:1858) (cid:1866) (cid:3404) (cid:1855)(cid:3041), (cid:1855) là hằng số >1. • Hàm giai thừa (cid:1858) (cid:1866) (cid:3404) (cid:1866)!

tiệm cận Ω, Ο khác nhau • Các lớp hàm thông dụng:

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

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

(cid:3034)(cid:4666)(cid:3041)(cid:4667) (cid:3033)(cid:4666)(cid:3041)(cid:4667)

• Quan hệ thống trị: • Cộng hai hàm (cid:1866)! ≫ (cid:1855)(cid:3041) ≫ (cid:1866)(cid:2871) ≫ (cid:1866)(cid:2870) ≫ (cid:1866)log(cid:1866) ≫ (cid:1866) ≫ log(cid:1866) ≫ 1 • Ο (cid:1858) (cid:1866) (cid:3397) Ο(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) → Ο(cid:4666)max (cid:1858) (cid:1866) , (cid:1859)(cid:4666)(cid:1866)(cid:4667) (cid:4667) • Giới hạn và quan hệ thống trị của các hàm • Ω (cid:1858) (cid:1866) (cid:3397) Ω(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) → Ω(cid:4666)max (cid:1858) (cid:1866) , (cid:1859)(cid:4666)(cid:1866)(cid:4667) (cid:4667) (cid:3404) 0 • (cid:1858)(cid:4666)(cid:1866)(cid:4667) thống trị (cid:1859)(cid:4666)(cid:1866)(cid:4667) nếu lim (cid:3041)→(cid:2998) • Θ (cid:1858) (cid:1866) (cid:3397) Θ(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) → Θ(cid:4666)max (cid:1858) (cid:1866) , (cid:1859)(cid:4666)(cid:1866)(cid:4667) (cid:4667)

(cid:3404) 3

(cid:3034)(cid:4666)(cid:3041)(cid:4667) (cid:3033)(cid:4666)(cid:3041)(cid:4667)

VD. (cid:1858) (cid:1866) (cid:3404) (cid:1866)(cid:2870) không thống trị (cid:1859) (cid:1866) (cid:3404) 3(cid:1866)(cid:2870) (cid:3397) 5 vì lim (cid:3041)→(cid:2998)

• Nhân hàm

(cid:3404) 0

(cid:3034)(cid:4666)(cid:3041)(cid:4667) (cid:3033)(cid:4666)(cid:3041)(cid:4667)

(cid:1858) (cid:1866) (cid:3404) (cid:1866)(cid:2870) thống trị (cid:1859) (cid:1866) (cid:3404) (cid:1866)(cid:2869).(cid:2877)(cid:2877)(cid:2877)(cid:2877)(cid:2877)(cid:2877) vì lim (cid:3041)→(cid:2998)

• Ο (cid:1855) ⋅ (cid:1858) (cid:1866) → Ο(cid:4666)(cid:1858)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

• Ω (cid:1855) ⋅ (cid:1858) (cid:1866) → Ω(cid:4666)(cid:1858)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

(cid:1855) là một hằng số dương bất kỳ

• Θ (cid:1855) ⋅ (cid:1858) (cid:1866) → Θ(cid:4666)(cid:1858)(cid:4666)(cid:1866)(cid:4667)(cid:4667) (cid:1866)! ≫ (cid:1855)(cid:3041) ≫ (cid:1866)(cid:2871) ≫ (cid:1866)(cid:2870) ≫ (cid:1866)(cid:2869)(cid:2878)(cid:3106) ≫ (cid:1866)log(cid:1866) ≫ (cid:1866) ≫ (cid:1866) ≫ log (cid:1866)(cid:2870) ≫ log(cid:1866) ≫ log(cid:1866)/loglog(cid:1866) ≫ loglog(cid:1866) ≫ 1

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

• Ο (cid:1858) (cid:1866) ∗ Ο(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) → Ο(cid:4666)(cid:1858) (cid:1866) ∗ (cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

• Nếu (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) và (cid:1859) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) thì (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) • Nếu (cid:1858) (cid:1866) (cid:3404) Ω(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) và (cid:1859) (cid:1866) (cid:3404) Ω(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) thì (cid:1858) (cid:1866) (cid:3404) Ω(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) • Nếu (cid:1858) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) và (cid:1859) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) thì (cid:1858) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) • Ω (cid:1858) (cid:1866) ∗ Ω(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) → Ω(cid:4666)(cid:1858) (cid:1866) ∗ (cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

• Θ (cid:1858) (cid:1866) ∗ Θ(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) → Θ(cid:4666)(cid:1858) (cid:1866) ∗ (cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) Tính đối xứng – symmetry • (cid:1858) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) khi và chỉ khi (cid:1859)(cid:4666)(cid:1866)(cid:4667) (cid:3404) Θ(cid:4666)(cid:1858)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

Tính đối xứng chuyển vị ‐ transpose symmetry • (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) khi và chỉ khi (cid:1859) (cid:1866) (cid:3404) Ω(cid:4666)(cid:1858)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

MỘT SỐ TÍNH CHẤT

MỘT SỐ VÍ DỤ

selection_sort(int s[], int n) {

int i,j; /* counters */ int min; /* index of minimum */ for (i=0; i

min=i; for (j=i+1; j

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

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

}

Thuật toán sắp xếp lựa chọn – Selection Sort Chứng minh Nếu (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) và (cid:1859) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) thì (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

}

Ta có • (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1859)(cid:4666)(cid:1866)(cid:4667)(cid:4667) tức là (cid:1858)(cid:4666)(cid:1866)(cid:4667) (cid:3409) (cid:1855)(cid:2869)(cid:1859)(cid:4666)(cid:1866)(cid:4667) với (cid:1866) (cid:3408) (cid:1866)(cid:2869) • (cid:1859) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667) tức là (cid:1859)(cid:4666)(cid:1866)(cid:4667) (cid:3409) (cid:1855)(cid:2870)(cid:1860)(cid:4666)(cid:1866)(cid:4667) với (cid:1866) (cid:3408) (cid:1866)(cid:2870) Suy ra • (cid:1858)(cid:4666)(cid:1866)(cid:4667) (cid:3409) (cid:1855)(cid:2869)(cid:1859)(cid:4666)(cid:1866)(cid:4667) (cid:3409) (cid:1855)(cid:2869)(cid:1855)(cid:2870)(cid:1860)(cid:4666)(cid:1866)(cid:4667) với (cid:1866) (cid:3408) max (cid:4666)(cid:1866)(cid:2869), (cid:1866)(cid:2870)(cid:4667) Chọn (cid:1855)(cid:2871) (cid:3404) (cid:1855)(cid:2869)(cid:1855)(cid:2870) và (cid:1866)(cid:2871) (cid:3404) max (cid:4666)(cid:1866)(cid:2869), (cid:1866)(cid:2870)(cid:4667) thì (cid:1858)(cid:4666)(cid:1866)(cid:4667) (cid:3409) (cid:1855)(cid:2871)(cid:1860) (cid:1866) khi (cid:1866) (cid:3408) (cid:1866)(cid:2871) Vậy (cid:1858) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1860)(cid:4666)(cid:1866)(cid:4667)(cid:4667)

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

…

Phân tích trong trường hợp tồi nhất • (cid:1861) (cid:3404) 0 lệnh if lặp (cid:1866) (cid:3398) 2 lần (từ 1 tới n‐1) • (cid:1861) (cid:3404) 1 lệnh if lặp (cid:1866) (cid:3398) 3 lần (từ 2 tới n‐1) • Vòng lặp ngoài lặp n lần (từ 0 tới n‐1)

• 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 • (cid:1861) (cid:3404) (cid:1866) (cid:3398) 2 lệnh if lặp 1 lần (từ n‐1 tới n‐1) • (cid:1861) (cid:3404) (cid:1866) (cid:3398) 1 lệnh if lặp 0 lần • 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 (cid:1846) (cid:1866) (cid:3404) (cid:1866) (cid:3398) 2 (cid:3397) (cid:1866) (cid:3398) 3 (cid:3397) ⋯ (cid:3397) 1 (cid:3397) 0 (cid:3404) (cid:4666)(cid:1866) (cid:3398) 2(cid:4667)(cid:4666)(cid:1866) (cid:3398) 1(cid:4667)/2 hợp tồi nhất là (cid:1866) (cid:3400) (cid:1866) → Ο(cid:4666)(cid:1866)(cid:2870)(cid:4667) • Vậy (cid:1846) (cid:1866) (cid:3404) Θ(cid:4666)(cid:1866)(cid:2870)(cid:4667)

MỘT SỐ VÍ DỤ

• Phân tích trong trường hợp tồi nhất • Sắp xếp chèn – Insertion Sort for (i=1; i0) && (s[j] < s[j‐1])) {

• (cid:1861) (cid:3404) (cid:1866) (cid:3398) 2 lệnh cơ sở lặp (cid:1866) (cid:3398) 2 lần • (cid:1861) (cid:3404) (cid:1866) (cid:3398) 1 lệnh cơ sở lặp (cid:1866) (cid:3398) 1 lần swap(&s[j],&s[j‐1]); j = j‐1; • Số lần lặp của lệnh cơ sở sẽ là } (cid:1846) (cid:1866) (cid:3404) 1 (cid:3397) 2 (cid:3397) ⋯ (cid:3397) (cid:1866) (cid:3398) 2 (cid:3397) (cid:1866) (cid:3398) 1 (cid:3404) (cid:1866) (cid:3398) 1 (cid:1866)/2 }

• Vậy (cid:1846) (cid:1866) (cid:3404) Ο(cid:4666)(cid:1866)(cid:2870)(cid:4667) • Lệnh được lặp nhiều nhất là 2 lệnh bên trong while : lệnh cơ sở

1/10/2011

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

• ∑ 1(cid:3029)

(cid:3028) (cid:3404) (cid:1854) (cid:3398) (cid:1853) (cid:3397) 1

• ∑ (cid:1861)(cid:3041)

(cid:3036)(cid:2880)(cid:2869) (cid:3404) 1 (cid:3397) 2(cid:3397). . (cid:3397)(cid:1866) (cid:3404)

(cid:3041) (cid:3041)(cid:2878)(cid:2869) (cid:2870)

• ∑ (cid:1862)(cid:3041)

(cid:3037)(cid:2880)(cid:3036) (cid:3404) (cid:1861) (cid:3397) (cid:1861) (cid:3397) 1 (cid:3397). . (cid:3397)(cid:1866) (cid:3404) ∑ (cid:1861)(cid:3041)

(cid:3036)(cid:2880)(cid:2869) (cid:3398) ∑

(cid:3036)(cid:2879)(cid:2869) (cid:3037)(cid:2880)(cid:2869) (cid:3404) (cid:1862)

(cid:3041)(cid:3118)(cid:2878)(cid:3041)(cid:2879)(cid:3036)(cid:3118)(cid:2878)(cid:3036) (cid:2870)

(cid:3041) (cid:3036)(cid:2880)(cid:2869) (cid:3404) 1(cid:2870) (cid:3397) 2(cid:2870) (cid:3397) 3(cid:2870)(cid:3397). . (cid:3397)(cid:1866)(cid:2870) (cid:3404) • ∑ (cid:1861)(cid:2870)

(cid:2870)(cid:3041)(cid:3119)(cid:2878)(cid:2871)(cid:3041)(cid:3118)(cid:2878)(cid:3041) (cid:2874)

• (cid:1853)(cid:2868) (cid:3397) (cid:1853)(cid:2869)(cid:3397). . (cid:3397)(cid:1853)(cid:3041) (cid:3404)

với (cid:1853) (cid:3405) 1

(cid:3028)(cid:3289)(cid:3126)(cid:3117)(cid:2879)(cid:2869) (cid:3028)(cid:2879)(cid:2869)

• ∑ (cid:1876)(cid:3036)(cid:2998)

nếu (cid:1876) (cid:3407) 1

(cid:3036)(cid:2880)(cid:2868) (cid:3404)

(cid:2869) (cid:2869)(cid:2879)(cid:3051)

(cid:3404) (cid:1855) (cid:3397) 2(cid:1855)(cid:2870)(cid:3397). . (cid:3397)(cid:1866)(cid:1855)(cid:3041) (cid:3404)

(cid:3041) • ∑ (cid:1861)(cid:1855)(cid:3036) (cid:3036)(cid:2880)(cid:2869)

(cid:3041)(cid:2879)(cid:2869) (cid:3030)(cid:3289)(cid:3126)(cid:3117)(cid:2879)(cid:3041)(cid:3030)(cid:3289)(cid:2878)(cid:3030) (cid:3030)(cid:2879)(cid:2869) (cid:3118)