BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Giáo viên:

Gmail: thayhuetnh@gmail.com

SĐT, Zalo: 0382.1682.32

Blog: thayhuetnh.blogspot.com

1

Chương II: CÁC KHÁI NIỆM VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

I. Lựa chọn thuật toán

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

A. Độ phức tạp không gian (bộ nhớ lưu trữ)

B. Độ phức tạp tính toán (thời gian)

1. Đánh giá thời gian thực hiện thuật toán

2. Xác định độ phức tạp tính toán của thuật toán

3. Một số hàm ký hiệu độ phức tạp thuật toán.

4. Các quy tắc đánh giá thời gian thực hiện thuật toán

5. Một số ví dụ

​

2

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

I. Lựa chọn thuật toán

- Khi giải một bài toán, chúng ta cần chọn trong số các thuật toán một thuật toán mà chúng ta cho là “tốt” nhất.

- Vậy dựa trên cơ sở nào để đánh giá thuật toán này “tốt” hơn thuật toán kia?

- Thông thường ta dựa trên hai tiêu chuẩn sau:

a. Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình).

b. Thuật toán hiệu quả: Chúng ta thường đặc biệt quan tâm đến thời gian thực hiện của thuật toán (gọi là độ phức tạp tính toán), bên cạnh đó chúng ta cũng quan tâm tới dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, ra và các kết quả trung gian trong quá trình tính toán.

3

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

I. Lựa chọn thuật toán

- Có nhiều ý kiến cho rằng: Kỹ thuật máy tính tiến bộ rất nhanh, ngày nay các máy tính lớn có thể đạt tốc độ tính toán hàng nghìn tỉ phép tính trong một giây. Vậy có cần phải tìm thuật toán hiệu quả với thời gian thực hiện thuật toán thấp hay không?

Ví dụ: một CPU có tốc độ xung nhịp 3.2 GHz thực hiện 3.2 tỷ chu kỳ mỗi giây. (Các CPU cũ hơn có tốc độ được đo bằng megahertz, hoặc hàng triệu chu kỳ mỗi giây.)

​

4

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

I. Lựa chọn thuật toán

- Chúng ta xem lại ví dụ bài toán kiểm tra tính nguyên tố của một số nguyên dương n (n ≥ 1).

- Đoạn code minh họa:

bool ktsnt(){

for (int i = 2; i <= n-1; i++){

if (n % i == 0)

      return 0;//n không là nguyên tố

}

return 1;//n là nguyên tố

}

- Nếu n là một số nguyên tố chúng ta phải mất n - 2 phép toán %.

- Để kiểm tra số nguyên N có 25 chữ số mất bao nhiêu thời gian?

5

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

6

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

7

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

https://codelearn.io/sharing/do-phuc-tap-cua-thuat-toan-va-lua-chon-cach-giai-thuat

https://vnoi.info/wiki/translate/topcoder/Computational-Complexity-Section-1.md

A. Độ phức tạp không gian (bộ nhớ lưu trữ)

- Độ phức tạp không gian của một thuật toán hoặc một chương trình máy tính là lượng không gian bộ nhớ cần thiết để giải quyết một trường hợp của bài toán tính toán dưới dạng một hàm của các đặc tính của đầu vào.

- Độ phức tạp không gian được đo bằng cách sử dụng ký hiệu tương tự như độ phức tạp thời gian, nhưng chúng ta xem xét tổng phân bổ bộ nhớ được yêu cầu, liên quan đến kích thước của dữ liệu đầu vào.

​

8

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

- Để giải một bài toán không chỉ có một giải thuật. Chọn một giải thuật đưa tới kết quả nhanh nhất là một đòi hỏi thực tế.

-Thời gian thực hiện 1 giải thuật bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố:

Một yếu tố cần chú ý đó là kích thước của dữ liệu đưa vào. Dữ liệu càng lớn thì thời gian xử lý càng chậm, chẳng hạn như thời gian sắp xếp một dãy số phải chịu ảnh hưởng của số lượng các số thuộc dãy số đó. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực hiện của một giải thuật có thể biểu diễn một cách tương đối như một hàm của n: T(n).

9

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

- Phần cứng máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện. Những yếu tố này không giống nhau trên các loại máy, vì vậy không thể dựa vào chúng khi xác định T(n).

- Tức là T(n) không thể biểu diễn bằng đơn vị thời gian: giờ, phút, giây được. Tuy nhiên, không phải vì thế mà không thể so sánh được các giải thuật về mặt tốc độ.

- Nếu như thời gian thực hiện một giải thuật là T₁ = n² và thời gian thực hiện giải thuật khác là T₂ (n) = 100n thì khi n đủ lớn, thời gian thực hiện giải thuật T₂ nhanh hơn T₁ .

Ví dụ: N=10000; T₁=100 000 000 T₂=1 000 000

10

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

>

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

- Khi đó, nếu nói rằng thời gian thực hiện giải thuật tỉ lệ thuận với n hay tỉ lệ thuận với n² cũng cho ta một cách đánh giá tương đối về tốc độ thực hiện của giải thuật đó khi n khá lớn. Cách đánh giá thời gian thực hiện giải thuật độc lập với máy tính và các yếu tố liên quan tới máy tính như vậy sẽ được gọi là độ phức tạp của thuật toán.

🡪 độ phức tạp của thuật toán có thời gian thực hiện T(n)

​

11

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

1. Đánh giá thời gian thực hiện thuật toán

- Có hai cách tiếp cận để đánh giá thời gian thực hiện của một thuật toán:

+ Cách thứ nhất: bằng thực nghiệm, chúng ta viết chương trình và cho chạy chương trình với các dữ liệu vào khác nhau trên một máy tính.

+ Cách thứ hai: bằng phương pháp lí thuyết, chúng ta coi thời gian thực hiện thuật toán như hàm số của cỡ dữ liệu vào (cỡ của dữ liệu vào là một tham số đặc trưng cho dữ liệu vào, nó có ảnh hưởng quyết định đến thời gian thực hiện chương trình)

​

12

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

1. Đánh giá thời gian thực hiện thuật toán

Ví dụ đối với bài toán kiểm tra số nguyên tố thì cỡ của dữ liệu vào là số n cần kiểm tra; hay với bài toán sắp xếp dãy số, cỡ của dữ liệu vào là số phần tử của dãy.

- Thông thường cỡ của dữ liệu vào là một số nguyên dương n, ta sử dụng hàm số T(n) trong đó n là cỡ của dữ liệu vào để biểu diễn thời thực hiện của một thuật toán.

- Chúng ta hiểu hàm số T(n) là thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào cỡ n.

​

​

13

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

1. Đánh giá thời gian thực hiện thuật toán

- Sử dụng ký hiệu toán học ô lớn (O) để mô tả độ lớn của hàm T(n). Giả sử n là một số nguyên dương, T(n) và f(n) là hai hàm thực không âm. Ta viết T(n) = O(f(n)) nếu tồn tại các hằng số dương c và n₀ , sao cho T(n) ≤ c.f(n), với mọi n ≥ n₀.

- Nếu một thuật toán có thời gian thực hiện T(n) = O(f(n)) chúng ta nói rằng thuật toán có thời gian thực hiện cấp f(n).

​

​

14

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

1. Đánh giá thời gian thực hiện thuật toán

Ví dụ 1: nếu T(n) = n² + 1, thì T(n) = O(n²)

🡪 chọn c = 2 và n₀ = 1, khi đó với mọi n ≥ 1

ta có: T(n) = n² + 1 ≤ 2n² = 2f(n).

Ví dụ 2: Giả sử T(n) = n² + 2n, ta có n² + 2n ≤ n² + 2n² với mọi n ≥ 1

🡪 Vậy T(n) = O(n²), trong trường hợp này ta nói thuật toán có thời gian thực hiện cấp n².

​

15

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

2. Xác định độ phức tạp tính toán của thuật toán:

Việc xác định độ phức tạp tính toán của thuật toán bất kỳ có thể rất phức tạp. Tuy nhiên độ phức tạp của một số thuật toán trên thực tế có thể tính bằng 1 số quy tắc đơn giản sau:

2.1. Quy tắc bỏ hằng số

Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(c1.f(n)) với c1 là một hằng số dương thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)).

Như vậy, hằng số ở đây không quan trọng.

T(n) = O(f(n))

​

16

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

2. Xác định độ phức tạp tính toán của thuật toán:

2.2. Quy tắc cộng

Nếu đoạn chương trình P₁ có thời gian thực hiện T₁(n) = O(f(n)) và đoạn chương trình P₂ có thời gian thực hiện là T₂(n) = O(g(n)), khi đó thời gian thực hiện thuật toán sẽ là:

T₁(n) + T₂(n) = O(f(n) + g(n))

2.3. Quy tắc lấy max

Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp thuật toán:

O(max(f(n) + g(n)))

​

17

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

2.3. Quy tắc lấy max.

Ví dụ 1: phân tích thời gian của đoạn chương trình sau:

{

cin>>n; //1

S1=0; //2

for (int i=1; i<=n; i++) //3

S1+ = i ; //4

S2 = 0; //5

for (int j=1; j<=n; j++) //6

S2+ = j*j; //7

cout<< “1+2+…+” << n << “=”<<s1<<endl; //8

cout<< “1^2+2^2+…+” << n << “^2=”<<s2<<endl; //9

}

18

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

O(1)

O(1)

O(n)

O(1)

O(1)

O(1)

O(1)

O(1)

O(n)

Max(O(1), O(1), O(n), O(1), O(1), O(n), O(1), O(1), O(1)) = O(n)

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

2.4. Quy tắc nhân.

- Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O(f(n)).

- Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với �k(n) = O(g(n)) thì độ phức tạp tính toán sẽ là O(g(n).f(n))

​

19

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

2.4. Quy tắc nhân.

Ví dụ 2: phân tích thời gian của đoạn chương trình sau:

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

cin>>a[i]; //2

for (int i=1; i<=n; i++) //3

for (int j=i; j<=n; j++) //4

if (a[i]>a[j]) //5

swap(a[i],a[j]); //6

}

​

20

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

O(1)

O(n)

O(1)

O(1)

O(n²)

O(n)

Max(O(n),O(1), O(n²), O(n), O(1), O(1)) = O(n²)

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

3. Một số hàm ký hiệu độ phức tạp thuật toán.

- Tùy vào dạng hàm f(n), ta có các ký pháp sau:

+ Nếu 1 thuật toán có thời gian thực hiện đa thức bậc k: P(n), thì độ phức tạp tính toán của thuật toán đó viết là O(n^k).

+ Nếu 1 thuật toán có thời gian thực hiện là log_af(n) với b là một số dương, ta nhận thấy log_af(n) = log_a b_logb f(n). Tức là: O(log_af(n)) = O(log_bf(n)). Vậy ta có thể nói rằng độ phức tạp tính toán của thuật toán đó là O(log f(n)) mà không cần ghi cơ số logarit.

​

21

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

3. Một số hàm ký hiệu độ phức tạp thuật toán.

- Nếu một thuật toán có độ phức tạp là hằng số, tức thời gian thực hiện không phụ thuộc vào kích thước dữ liệu vào thì ta ký hiệu độ phức tạp thuật toán đó là O(1).

- Một số hàm thường dùng để chỉ lớp bài toán với độ phức tạp của thuật toán là logn, n, nlogn, n², n³, 2ⁿ. Tên gọi hàm thường dùng để chỉ lớp bài toán có độ phức tạp tương ứng.

​

22

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

3. Một số hàm ký hiệu độ phức tạp thuật toán.

Ví dụ: Nói độ phức tạp tính toán của thuật toán này là đa thức, của thuật toán kia là hàm mũ.

- Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và bảng giá trị của chúng để tiện theo dõi sự tăng của hàm theo đối số n.

​

23

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

4. Các quy tắc đánh giá thời gian thực hiện thuật toán

- Để đánh giá, chúng ta phân tích chương trình xuất phát từ các lệnh đơn, rồi đánh giá các lệnh phức tạp hơn, cuối cùng đánh giá được thời gian thực hiện của chương trình, cụ thể:

- Thời gian thực hiện các lệnh đơn: gán, đọc, viết là O(1)

• Lệnh hợp thành (câu lệnh ghép): giả sử thời gian thực hiện của S1, S2,…,Sm tương ứng là O(f₁(n)), O(f₂(n)),…, O(f_m(n)),. Khi đó thời gian thực hiện của lệnh hợp thành là: O(max((f₁(n), (f₂(n),…, f_m(n))).
• Lệnh If: giả sử thời gian thực hiện của S₁, S₂ tương ứng là O(f₁(n)), O(f₂(n)). Khi đó thời gian thực hiện của lệnh If là: O(max(f₁(n), f₂(n))).

24

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

B. Độ phức tạp tính toán (thời gian)

4. Các quy tắc đánh giá thời gian thực hiện thuật toán

• Lệnh lặp While: giả sử thời gian thực hiện lệnh S (thân của lệnh While) là O(f(n)) và g(n) là số lần lặp tối đa thực hiện lệnh S. Khi đó thời gian thực hiện lệnh While là O(f(n)g(n))
• Lệnh lặp For: giả sử thời gian thực hiện lệnh S là O(f(n)) và g(n) là số lần lặp tối đa. Khi đó thời gian thực hiện lệnh For là O(f(n)g(n))

25

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

​

26

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II

Giá trị N lớn nhất để các thuật toán có độ phức tạp khác nhau chạy trong tối đa 8 giây

BÀI 4: ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Củng cố

I. Lựa chọn thuật toán

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

A. Độ phức tạp không gian

B. Độ phức tạp tính toán (thời gian)

1. Đánh giá thời gian thực hiện thuật toán

2. Xác định độ phức tạp tính toán của thuật toán

3. Một số hàm ký hiệu độ phức tạp thuật toán.

4. Các quy tắc đánh giá thời gian thực hiện thuật toán

5. Một số ví dụ

27

Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên

Tổ Tin học Chương II