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

 

1 thuật toán hiệu quả thì quan trọng trong sản phẩm. Nó quyết định đến sự ổn định, chất lượng của sản phẩm

I. Khái niệm

        - Time complexity(độ phức tạp của thuật toán)

II. Cách tính toán

1. Tính toán chung

O(1): truy cập trực tiếp phần tử của mảng

O(n): 1 vòng lặp for chạy n lần, đệ quy

O(n2): 2 vòng lặp for lồng nhau

O(n3): 3 vòng lặp for lồng nhau

O(m*n): 2 vòng lặp for lồng nhau với 2 biến m,n

O(2^n): Đệ quy gọi 2 lần

O(n!): bài toán hoán vị

O(log(n)): Binary search

O(căn bậc 2 n): số nguyên tố

O(n log n): merge sort, quick sort

với các hằng số nhỏ thì bỏ qua:

for(i=0;i<3*n;i++) -> O(n)

for(i=0;i<n+5;i++) -> O(n)

for(i=0;i<n/2;i++) -> O(n)

2. với 1 chuỗi các phép toán, độ phức tạp sẽ là của thuật toán chạy chậm nhất

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

{//code

}

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

{

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

}

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

{

//code

}

-> O(n2)

linear recursion

void g(int n)

{

if(n==1) return;

g(n-1);

}

-> O(n)

binary recursion

void g(int n)

{

if(n==1) return;

g(n-1);

g(n-1);

}

-> O(2^n)

III. Ước lượng tính hiệu quả của thuật toán

1. Ví dụ

 - Máy tính bình thường có thể thực hiện 10^8 phép tính/giây. Giả sử thuật toán đó chỉ được phép chạy trong 1s và đầu vào là 10^6

- Lựa chọn thuật toán:

• chọn O(n2) -> 10^12 -> quá chậm, không thỏa mãn
• chọn O(n log n) -> 10^6 * 20 = 2 *10^7 -> chấp nhận

2. Một vài rule chung

+ n<=10 -> O(n!)

+ n<=20 -> O(2^n)

+ n<=5000 -> O(n2)

+ n<=10^6 -> O(n logn) hoặc O(n)

+ n is large -> O(1) hoặc O(log(n))