Hiển thị các bài đăng có nhãn algorithm. Hiển thị tất cả bài đăng
Hiển thị các bài đăng có nhãn algorithm. Hiển thị tất cả bài đăng
Mở đầu
Là một lập trình viên, chắc hẳn bạn đã từng ít nhiều nghe tới khái niệm "Độ phức tạp của thuật toán". Rất nhiều người cho rằng độ phức tạp của thuật toán đại diện cho thời gian chạy nhanh hay chậm của 1 chương trình, nhưng liệu đây có phải là 1 quan niệm đúng? Bài viết dưới đây sẽ cho bạn cái nhìn tổng quan về độ phức tạp của 1 thuật toán.Tại sao cần đo độ phức tạp của thuật toán
Thông thường khi giải quyết 1 bài toán, chúng ta có thể đưa ra các giải thuật khác nhau nhưng sẽ phải chọn một giải thuật tốt nhất. Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:- Giải thuật đúng đắn.
- Giải thuật đơn giản.
- Giải thuật thực hiện nhanh.
Đối với các chương trình chỉ dùng 1 vài lần thì yêu cầu giải thuật đơn giản sẽ được ưu tiên vì chúng ta cần 1 giải thuật dễ hiểu, dễ cài đặt, ở đây không đề cao vấn đề thời gian chạy vì chúng ta chỉ chạy 1 vài lần.
Tuy nhiên, khi 1 chương trình sử dụng nhiều lần, yêu cầu tiết kiệm thời gian sẽ được đặc biệt ưu tiên. Tuy nhiên, thời gian thực hiện chương trình lại phụ thuộc vào rất nhiều yếu tố như: cấu hình máy tính, ngôn ngữ sử dụng, trình biên dịch, dữ liệu đầu vào, ... Do đó ta khi so sánh 2 giải thuật đã được implement, chưa chắc chương trình chạy nhanh hơn đã có giải thuật tốt hơn. "Độ phức tạp của thuật toán" sinh ra để giải quyết vấn đề này.
Cách để tính độ phức tạp của thuật toán
Độ phức tạp của một thuật toán là 1 hàm phụ thuộc vào độ lớn của dữ liệu đầu vào.Tìmxem 1 đối tượng có trong danh sách N phần tử hay không?, sắp xếp tăng dần dãy số
gồm N số, ... N ở đây chính là độ lớn của dữ liệu đầu vào
Để ước lượng độ phức tạp của một thuật toán, người ta thường dùng khái niệm bậc O-lớn và bậc Theta (Θ)
1. Big O
Ở đây ta dùng một đại lượng tổng quát là tài nguyên cần dùng R(n). Đó có thể là số lượng phép tính (có thể tính cả số lần truy nhập bộ nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là thời gian thực hiện chương trình (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần phải cấp để chạy chương trình (độ phức tạp về không gian).1.1 Định nghĩa
Giả sử f(n) và g(n) là các hàm thực không âm của đối số nguyên không âm n. Ta nói "g(n) là O của f(n)" và viết là: g(n) = O(f(n)) nếu tồn tại các hằng số dương C và n0 sao cho g(n) <= C * f(n) với mọi n >= n0
1.2 Cách tính
Độ phức tạp tính toán của giải thuật: O(f(n))• Việc xác định độ phức tạp tính toán của giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản sau:
– Quy tắc bỏ hằng số:
T(n) = O(c.f(n)) = O(f(n)) với c là một hằng số dương– Quy tắc lấy max:
T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n)))– Quy tắc cộng:
T1(n) = O(f(n))– Quy tắc nhân:
T2(n) = O(g(n))
T1(n) + T2(n) = O(f(n) + g(n))
Đoạn chương trình có thời gian thực hiện T(n)=O(f(n))
Nếu thực hiện k(n) lần đoạn chương trình với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n))
1.3 Ví dụ
Ví dụ 1:s = n * (n-1) /2;Trong ví dụ trên, độ phức tạp của thuật toán là O(1)
Ví dụ 2:
s = 0; // O(1)
for (i=0; i<=n;i++){
p = 1; // O(1)
for (j=1;j<=i;j++)
p = p * x / j; // O(1)
s = s+p; // O(1)
}
Số lần thực hiện phép toán p = p * x / j là n(n-1) / 2=> Độ phức tạp của đoạn code này là O(1) + O(1) + O(n(n-1)/2) + O(1) + O(1) = O(n2)
Ví dụ 3:
for (i= 1;i<=n;i++) {
for (u= 1;u<=m;u++)
for (v= 1;v<=n;v++)
//lệnh
for j:= 1 to x do
for k:= 1 to z do
//lệnh
}
=> Độ phức tạp của thuật toán này là: O(nmax(nm, x*z))2. Theta và Omega
Tương tự như Big O, nếu như tìm được các hằng số C, k1, k2 đều dương, không phụ thuộc vào n, sao cho với các số n đủ lơn, các hàm R(n), f(n) và h(n) đều dương và R(n) >= C.f(n) va k1.h(n) =< R(n) <= k2.h(n) thì ta nói thuật toán có độ phức tạp cỡ lớn hơn Omega(f(n)) và đúng bằng cỡ Theta(h(n))Chúng ta có thể hiểu Big(O), Omega, Theta như những hàm tiềm cận của hàm tính độ phức
tạp của thuật toán.
Kết luận
Bài viết trên đã đưa ra 1 cái nhìn tổng quan về độ phức tạp của thuật toán. Rằng đó không chỉ đại diện cho thời gian chạy nhanh/ chậm của 1 chương trình mà nó đại diện cho những động thái của hệ thống khi kích thước đầu vào tăng lên.Hy vọng sau bài viết này, mỗi khi bạn đặt tay viết 1 đoạn chương trình nào đó,
hãy cân nhắc, tính toán để đoạn chương trình có độ phức tạp trong mức cho phép.
Cám ơn các bạn đã dành thời gian đọc bài.
Nguồn tham khảo:
CÂU CHUYỆN
Trong một buổi phỏng vấn kỹ thuật tại công ty XXX, một lập trình viên “lão thành” chịu trách nhiệm phỏng vấn Tèo hỏi Tèo một câu:“Hãy viết chương trình C tính căn bậc 2 của số nguyên x”
Tèo cười thầm và tự nghĩ “Công ty công nghệ hàng đầu Việt Nam gì mà hỏi một câu dễ vậy. Nó đâu phải là thằng mới học lập trình!”
Và Tèo trong chớp mắt đưa ra ngay lời giải với đoạn code như dưới đây:
#include <stdio.h>
#include <math.h>
int main()
{
int x;
printf("Input x: ");
scanf("%d", &x);
printf("Sqrt of %d = %f\n", x, sqrt(x));
}
Input x: 3 Sqrt of 3 = 1.732051Chương trình compiled không có 1 lỗi và kết quả đúng.
Tèo tự tin. Không ngờ công ty XXX nổi tiếng mà lại hỏi một câu ngớ ngẩn đến thế! Nó nghĩ.
Lập trình viên kinh nghiệm nhìn code của Tèo và khen: “Cậu có căn bản!”. Tèo sung sướng và nghĩ rằng mình đã chắc chắn 100% được nhận vào làm việc. Đúng lúc đấy vị lập trình viên già kia hỏi tiếp:
“Cậu hãy trả lời lại câu hỏi trên, lần này không dùng hàm sqrt của thư viện C”
“Chà câu hỏi có vẻ khó hơn. Tèo bắt đầu suy nghĩ. Sau một lúc cậu bắt đầu gãi đầu gãi tai. Làm thế nào để tính bây giờ? Tèo nghĩ mãi nghĩ mãi…”
Hết giờ! Người phỏng vấn Tèo nhận xét: “Cậu vẫn còn phải học nhiều”. Tèo buồn bã vì biết rằng mình đã trượt. Tuy vậy, nó nghĩ dù trượt nhưng nó nên ra về biết thêm 1 điều gì mới, nó liền hỏi người phỏng vấn:
“Làm thế nào tôi có thể tính được căn bậc hai? Phải chăng tôi cần một thuật toán phức tạp với rất nhiều dòng mã?”.
Vị lập trình viên “lão thành” cười và trả lời: “Máy tính làm phép tính rất nhanh, thay vì có câu trả lời tuyệt đối, ta có thể bắt nó đoán câu trả lời cho ta!”. Nhìn mặt Tèo lớ ngớ, vị kỹ sư già vừa cười vừa từ tốn giải thích tiếp.
Căn bậc hai của y được định nghĩa là số x sao cho: x^2 == y hay x = y / x. Nếu x là kết quả thì x = y / x, còn nếu không kết quả sẽ phải là 1 số x’ nằm trong khoảng x và y/x. Ta không biết số này là bao nhiêu, nhưng ta có 1 cách để đoán lấy 1 số trong khoảng này đó là trung bình cộng!
Tèo gật gù.
Ví dụ: cần tính căn bậc 2 của 3. Ta đoán kết quả là 1.0. Kết quả này không đúng rồi, nên đáp số sẽ nằm trong khoảng 1.0 và 3/1.0 = 2.0. Lấy trung bình cộng lần 1 ta có kết quả là 1.5. Lại thử với 1.5 và 3/1.5 = 2.0 ta có kết quả là 1.75! Sau nhiều lần lặp ta sẽ có kết quả tiệm cận với đáp số!
Tèo sáng mắt! Vị kỹ sư cười và tiếp tục.
Vì ta không có kết quả chính xác, nên số lần lặp sẽ là vô hạn. Tuy vậy tại mỗi bước lặp, ta sẽ thử xem kết quả đủ chính xác theo yêu cầu chưa. Ví dụ nếu đáp số hiện tại là x = 1.73, x^2 = 2.99 và ta chỉ cần độ chính xác đến 2 số sau dấu phẩy, thì 1.73 là đáp án phù hợp. Do vậy ta sẽ có chương trình tính căn bậc 2 như sau:
#include <stdio.h>
#include <math.h>
#define PRECISE 0.0001f
double mysqrt(int x)
{
double guess = 1.0f;
while (fabs(guess*guess - x)/x >= PRECISE)
guess = (x/guess - guess) / 2 + guess;
//or guess = (x/guess + guess) / 2;
return guess;
}
int main(void)
{
int x;
printf("Input x: ");
scanf("%d", &x);
printf("Sqrt of %d = %f\n", x, mysqrt(x));
return 0;
}
Input x: 3 Sqrt of 3 = 1.732051
Tham khảo
Theo : ktmt.github.io