Giới thiệu độ phức tạp thuật toán

#include <bits/stdc++.h>
using namespace std;

bool so_nt(long long x) {
    if (x < 2) { 
        return false; 
    }
    for (long long i = 2; i < x; i++) {
        if (x % i == 0) { 
            return false; 
        }
    }
    return true;
}
int main() {
    long long n;
    cin >> n;
    if (so_nt(n) == true) {
        cout << n << " la so nguyen to.";
    } else {
        cout << n << " khong la so nguyen to.";
    }
    return 0;
}

Trước hết, hãy thử chạy chương trình trên với đầu vào sau:

10000000000000061

Sau khi nhập số trên, chương trình sẽ không in ra kết quả gì và cũng không có thông báo được in ra, lí do là chương trình vẫn đang trong quá trình chạy.

Một máy tính thông thường có thể chạy được \(10^8\) (một trăm triệu) câu lệnh trong vòng 1 giây. Số \(x\) ở đầu vào phía trên là \(10000000000000061\), xấp xỉ \(10^{16}\). Như vậy, để có thể chạy vòng lặp for duyệt từ \(2\) đến \(x\), chương trình sẽ phải mất tới \(10^{16} / 10^{8} = 10^{8}\) giây, tức hơn 3 năm!

#include <bits/stdc++.h>
using namespace std;

bool so_nt(long long x) {
    if (x < 2) { 
        return false; 
    }
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) { 
            return false; 
        }
    }
    return true;
}
int main() {
    long long n;
    cin >> n;
    if (so_nt(n) == true) {
        cout << n << " la so nguyen to.";
    } else {
        cout << n << " khong la so nguyen to.";
    }
    return 0;
}

10000000000000061

10000000000000061 la so nguyen to.

Chương trình trên thay đổi điều kiện của vòng lặp so với Ví dụ 1. Điều kiện i * i <= x đảm bảo ta chỉ thực hiện vòng lặp đến căn bậc hai của \(x\). Bởi, nếu \(n\) có một ước số lớn hơn \(\sqrt{x}\), thì nó phải đi cùng một ước nhỏ hơn \(\sqrt{x}\). Do đó nếu không có ước nào từ \(2\) đến \(\sqrt{x}\), thì chắc chắn không có ước nào lớn hơn. Sau khi sửa điều kiện lặp, chương trình giờ chỉ còn chạy trong khoảng 1 giây!

Hành trình từ "chạy được" đến "chạy tốt"

Việc viết lại một chương trình để nó thực thi cùng một chức năng nhưng với hiệu suất vượt trội được gọi là tối ưu chương trình. Ở bề mặt, điều này nghe có vẻ đơn giản, nhưng nó đại diện cho một bước nhảy vọt về tư duy và kĩ năng. Bất kì ai có kiến thức cơ bản về lập trình đều có thể viết ra một chương trình "chạy được" – tức là cho ra kết quả đúng. Tuy nhiên, để tạo ra một chương trình "chạy tốt", một chương trình không chỉ đúng mà còn nhanh và hiệu quả khi dữ liệu đầu vào tăng lên thì lập trình viên cần đạt được một trình độ hoàn toàn khác.

Để đo lường sự "tốt" này một cách khách quan, chúng ta sử dụng khái niệm độ phức tạp thuật toán. Khái niệm này mô tả cách thời gian chạy hoặc mức sử dụng bộ nhớ thay đổi khi kích thước dữ liệu đầu vào lớn dần. Ví dụ, một thuật toán kém hiệu quả có thể khiến thời gian chạy tăng theo bình phương số lượng dữ liệu (khi dữ liệu tăng 10 lần, thời gian chạy tăng đến 100 lần). Hành trình tối ưu, về bản chất, chính là tìm kiếm một thuật toán thông minh hơn để thay thế, có thời gian chạy chỉ tăng tuyến tính (dữ liệu tăng 10 lần, thời gian chỉ tăng 10 lần), hoặc thậm chí còn tốt hơn.

Tối ưu chương trình - Một thử thách khó khăn

Tối ưu chương trình khó hơn việc viết mã ban đầu rất nhiều vì nó không còn là vấn đề của cú pháp, mà là sân chơi của chiến lược và kinh nghiệm.

• Xác định "nút thắt cổ chai": Một chương trình lớn có hàng nghìn dòng mã. Nỗ lực tối ưu sẽ vô nghĩa nếu bạn không xác định chính xác được đâu là đoạn mã có tốc độ xử lí chậm đi một cách đột biến khi dữ liệu lớn. Việc tìm ra "nút thắt cổ chai" này đòi hỏi kĩ năng phân tích, công cụ chuyên dụng và kinh nghiệm để nắm bắt dòng chảy của dữ liệu. Tối ưu sai chỗ cũng giống như việc sơn lại một chiếc xe để mong nó chạy nhanh hơn.
• Sự đánh đổi phức tạp: Tối ưu luôn đi kèm với sự đánh đổi, thường là giữa hiệu suất về thời gian và mức độ sử dụng bộ nhớ. Một lập trình viên phải cân nhắc: Liệu việc làm cho chương trình chạy nhanh hơn có đáng để hi sinh một lượng lớn bộ nhớ không? Quyết định đúng đắn đòi hỏi tầm nhìn xa và sự am hiểu về mục tiêu dài hạn của dự án.
• Yêu cầu kiến thức chuyên sâu: Tối ưu hiệu quả bắt buộc lập trình viên phải hiểu rõ cách các cấu trúc dữ liệu và giải thuật hoạt động. Quan trọng hơn, họ phải có khả năng phân tích được tốc độ tăng trưởng hiệu năng của chúng. Một lập trình viên giỏi phải nhận biết được khi nào một giải pháp có thời gian chạy tăng theo cấp số nhân là không thể chấp nhận, và phải tìm cách cải tiến nó bằng một thuật toán khác mà thời gian chạy chỉ tăng tuyến tính hoặc chậm hơn, để hệ thống có thể chịu được tải lớn.

Thước đo trình độ và lợi thế cạnh tranh

Trong thế giới công nghệ, khả năng tối ưu chính là một trong những thước đo rõ ràng nhất về trình độ của một lập trình viên. Các công ty công nghệ hàng đầu không chỉ tìm kiếm những người biết viết mã; họ săn lùng những kĩ sư có khả năng xây dựng các hệ thống hiệu quả, có thể phục vụ hàng tỉ người dùng một cách trơn tru.

Trong các buổi phỏng vấn kĩ thuật, các bài toán thường yêu cầu ứng viên không chỉ đưa ra một lời giải "chạy được", mà còn phải phân tích được hiệu suất của lời giải đó khi dữ liệu tăng lên và tìm cách tối ưu nó. Điều này giúp nhà tuyển dụng phân biệt ai là người chỉ có thể giải quyết vấn đề ở quy mô nhỏ và ai là người có tư duy để xây dựng các giải pháp bền vững ở quy mô lớn. Một lập trình viên có khả năng tối ưu tốt có thể mang lại lợi ích khổng lồ cho công ty:

• Tiết kiệm chi phí: Một hệ thống được tối ưu tốt cần ít tài nguyên máy chủ hơn để hoạt động, giúp tiết kiệm hàng triệu đô la chi phí vận hành.
• Nâng cao trải nghiệm người dùng: Một ứng dụng web tải nhanh, một trò chơi mượt mà sẽ giữ chân người dùng và tạo ra lợi thế cạnh tranh so với các đối thủ chậm chạp.
• Tạo nền tảng cho sự phát triển: Một mã nguồn hiệu quả là nền móng vững chắc để xây dựng thêm các tính năng mới mà không làm sụp đổ toàn bộ hệ thống.

Vì vậy, việc theo đuổi kĩ năng tối ưu không chỉ là một thử thách kĩ thuật, mà còn là con đường để một lập trình viên khẳng định giá trị bản thân và trở thành một tài sản không thể thiếu của bất kì tổ chức công nghệ nào.

Nội dung Độ phức tạp thuật toán và Tối ưu chương trình sẽ được giới thiệu rõ ràng và chi tiết trong quyển sách về các kiến thức lập trình thi đấu cơ bản, thuộc cùng bộ Giáo trình với Lập trình C++ cơ bản. Quyển sách dành cho các bạn yêu thích và mong muốn tham gia các kì thi lập trình thi đấu như Học sinh Giỏi, Tin học trẻ, Olympic, \(\ldots\) Nhóm tác giả HNCode rất mong các độc giả đón đọc!