Thuật toán và lưu đồ

Đến đây ta đã biết máy tính làm việc với bit. Nhưng con người không thể ngồi viết từng dãy 0 và 1 để ra lệnh cho máy, việc đó vừa chậm vừa dễ sai. Thay vào đó, ta viết lệnh bằng một ngôn ngữ lập trình gần với ngôn ngữ tự nhiên hơn, ví dụ ngôn ngữ C mà môn học này dạy. Nhưng trước khi viết được chương trình, ta phải có lời giải cho bài toán đã. Lời giải đó chính là thuật toán. Bài học này trả lời ba câu hỏi: thuật toán là gì, mô tả nó bằng những cách nào, và quy trình xây dựng một chương trình ra sao.

Lập trình là gì

Con người không ra lệnh cho máy bằng dãy bit thô. Thay vào đó, ta dùng một ngôn ngữ lập trình (programming language) để viết lệnh, rồi một phần mềm đặc biệt gọi là trình biên dịch (compiler) sẽ dịch những lệnh đó thành dãy bit mà máy hiểu được.

Lập trình (programming) là việc dùng một ngôn ngữ lập trình để viết ra một dãy lệnh có thứ tự, gọi là chương trình (program), nhằm yêu cầu máy tính thực hiện một công việc nào đó. Một chương trình giống như một công thức nấu ăn: nó liệt kê các bước cần làm, theo đúng thứ tự, để đạt được kết quả mong muốn.

Thuật toán là gì

Thuật toán (algorithm) là một dãy hữu hạn các bước được sắp xếp theo trình tự rõ ràng, nhằm giải quyết một bài toán. Mỗi bước phải xác định, có thể thực hiện được, và sau hữu hạn bước thuật toán phải dừng và cho kết quả.

Một thuật toán đúng đắn có các tính chất quan trọng sau:

• Tính xác định: mỗi bước phải rõ ràng, không mơ hồ, ai làm cũng cho cùng một kết quả.
• Tính hữu hạn: thuật toán phải kết thúc sau một số hữu hạn bước, không lặp vô tận.
• Tính đúng đắn: với dữ liệu vào hợp lệ, thuật toán cho ra đúng kết quả mong muốn.
• Có dữ liệu vào và ra: thuật toán nhận một số dữ liệu đầu vào và sản sinh ít nhất một kết quả đầu ra.

Bốn tính chất của một thuật toán đúng đắn

Một việc đời thường cũng có thể là một thuật toán. Pha một ly trà nóng có thể mô tả thành thuật toán: (1) đun nước sôi; (2) cho trà vào ly; (3) rót nước sôi vào ly; (4) chờ ba phút; (5) lấy bã trà ra. Năm bước rõ ràng, theo thứ tự, có điểm dừng. Lập trình về bản chất là kỹ năng diễn đạt những lời giải như vậy đủ chặt chẽ để máy làm theo.

Nhưng hãy thử nghiêm khắc với chính ví dụ vừa rồi. Bước "đun nước sôi" có thật sự xác định không? Đun bao nhiêu nước, tới bao nhiêu độ, bằng cái gì? Một con người tự lấp những khoảng trống ấy bằng kinh nghiệm, còn máy tính thì không. Máy không suy đoán ý định của bạn, nó thực hiện đúng cái bạn viết, kể cả khi cái bạn viết là một điều vô lý. Toàn bộ nỗi khổ của người mới học lập trình đều bắt nguồn từ khoảng cách giữa "điều tôi muốn nói" và "điều tôi thật sự đã viết ra".

Tính hữu hạn cũng đáng soi kỹ tương tự. Một dãy lệnh chạy mãi không dừng thì không phải thuật toán, dù mỗi bước riêng lẻ đều rõ ràng. Kinh nghiệm rút ra: mỗi khi viết một vòng lặp, hãy chỉ ra cho được đại lượng nào đang tiến dần về điều kiện dừng. Nếu bạn không chỉ ra được, rất có thể vòng lặp đó không dừng. Còn tính đúng đắn thì không đồng nghĩa với "chạy ra kết quả": một thuật toán có thể chạy trơn tru và in ra một con số sai. Người bảo đảm tính đúng đắn là bạn, bằng lập luận và kiểm thử, hai thứ sẽ bàn ở cuối bài.

Ba cách mô tả thuật toán

Cùng một thuật toán có thể trình bày bằng nhiều cách. Ba cách phổ biến nhất là liệt kê bước, lưu đồ và mã giả. Ta sẽ minh hoạ cả ba bằng cùng một bài toán quen thuộc: tìm số lớn hơn trong hai số a và b.

Cách 1: liệt kê các bước

Cách đơn giản nhất là viết tuần tự từng bước bằng lời:

1. Bắt đầu.
2. Nhập hai số a và b.
3. Nếu a lớn hơn b thì gán max bằng a, ngược lại gán max bằng b.
4. Thông báo max là số lớn hơn.
5. Kết thúc.

Cách này dễ đọc nhưng khi bài toán có nhiều rẽ nhánh và vòng lặp thì lời văn trở nên rối. Khi đó lưu đồ tỏ ra trực quan hơn.

Cách 2: lưu đồ

Lưu đồ (flowchart) biểu diễn thuật toán bằng các hình khối nối với nhau bằng mũi tên chỉ hướng đi của luồng thực hiện. Mỗi loại hình mang một ý nghĩa quy ước:

Hình	Ý nghĩa
Hình bo tròn hai đầu	điểm bắt đầu hoặc kết thúc (terminal)
Hình bình hành	nhập hoặc xuất dữ liệu (input/output)
Hình chữ nhật	một bước xử lý, tính toán (process)
Hình thoi	một câu hỏi rẽ nhánh, trả lời đúng hoặc sai (decision)
Mũi tên	hướng đi của luồng thực hiện

Vì site này dùng văn bản tĩnh, ta mô tả lưu đồ tìm số lớn hơn bằng cách liệt kê các khối theo luồng đi. Hãy đọc nó từ trên xuống: gặp hình thoi thì rẽ nhánh tùy câu trả lời đúng hay sai, rồi cả hai nhánh cùng đi tới điểm kết thúc.

[Bắt đầu]
    |
    v
[Nhập a, b]            (hình bình hành: nhập dữ liệu)
    |
    v
< a > b ? >            (hình thoi: câu hỏi rẽ nhánh)
   /   \
 đúng   sai
  |      |
  v      v
[max=a] [max=b]        (hình chữ nhật: bước xử lý)
   \    /
    \  /
     v
[Xuất max]             (hình bình hành: xuất dữ liệu)
    |
    v
[Kết thúc]

Hai nhánh đúng và sai chạy song song rồi cùng gặp lại ở khối xuất max. Đó chính là điểm mạnh của lưu đồ: nhìn là thấy ngay luồng đi và chỗ rẽ nhánh.

Cách 3: mã giả

Mã giả (pseudocode) là cách viết thuật toán theo phong cách gần với ngôn ngữ lập trình nhưng vẫn dùng từ ngữ tự nhiên, không ràng buộc cú pháp cụ thể của ngôn ngữ nào. Mã giả là cầu nối giữa cách diễn đạt bằng lời và code thật.

Doc a, b
Neu a > b thi
    max <- a
Nguoc lai
    max <- b
Het neu
Xuat max

Ký hiệu <- nghĩa là phép gán, tức đặt giá trị bên phải vào biến bên trái. Ba cách trên cùng mô tả một thuật toán; chọn cách nào là tùy mức độ phức tạp và sở thích người viết.

Để thấy mã giả gần code thật tới đâu, đây là cùng thuật toán đó viết bằng C:

#include <stdio.h>

int main(void) {
    int a, b, max;

    printf("Enter a and b: ");
    scanf("%d %d", &a, &b);

    if (a > b) {
        max = a;
    } else {
        max = b;
    }

    printf("The larger value is %d\n", max);
    return 0;
}

So sánh đoạn C với mã giả phía trên, bạn sẽ thấy từng dòng tương ứng gần như một đối một. Đó là lý do người lập trình giỏi thường phác mã giả trước khi gõ code.

Ghi nhớ

Lưu đồ mạnh ở chỗ trực quan, nhìn là thấy luồng đi. Mã giả mạnh ở chỗ gần với code, dễ chuyển thành chương trình thật. Người lập trình giỏi thường phác lưu đồ hoặc mã giả trước khi gõ một dòng code nào.

Các bước xây dựng chương trình

Viết một chương trình không phải là ngồi gõ code ngay từ đầu. Một quy trình hợp lý gồm các bước sau:

1. Xác định bài toán: hiểu rõ dữ liệu vào là gì, kết quả ra mong muốn là gì, có ràng buộc gì.
2. Thiết kế thuật toán: nghĩ ra lời giải và mô tả bằng liệt kê bước, lưu đồ hoặc mã giả.
3. Viết chương trình: chuyển thuật toán thành code bằng ngôn ngữ lập trình, ở đây là C.
4. Biên dịch và chạy thử: dùng trình biên dịch dịch code, rồi chạy với dữ liệu mẫu.
5. Kiểm thử và sửa lỗi: thử nhiều bộ dữ liệu, tìm và sửa các lỗi (bug), kể cả những trường hợp đặc biệt.
6. Bảo trì: chỉnh sửa, cải tiến chương trình khi yêu cầu thay đổi.

Sáu bước xây dựng một chương trình

🎯

Xác định bài toán

Rõ dữ liệu vào, kết quả ra, ràng buộc.

→

📝

Thiết kế thuật toán

Liệt kê bước, lưu đồ hoặc mã giả.

→

⌨️

Viết chương trình

Chuyển thuật toán thành code C.

→

⚙️

Biên dịch và chạy thử

Dịch code rồi chạy với dữ liệu mẫu.

→

🐞

Kiểm thử và sửa lỗi

Thử nhiều bộ dữ liệu, tìm và sửa lỗi.

→

🔧

Bảo trì

Chỉnh sửa, cải tiến khi yêu cầu thay đổi.

Đừng bỏ qua khâu thiết kế

Người mới rất hay bỏ qua hai bước đầu, lao vào gõ code rồi mới nghĩ. Hệ quả là code rối, khó sửa. Hãy tập thói quen viết ra thuật toán trước. Một phút suy nghĩ trên giấy tiết kiệm rất nhiều giờ gỡ lỗi.

Tư duy chia nhỏ bài toán

Khi gặp một bài toán lớn, đừng cố giải hết trong một lần. Hãy chia nó thành các bài toán con nhỏ hơn, giải từng phần, rồi ghép lại. Cách tiếp cận này gọi là chia để trị (divide and conquer) và là một thói quen tư duy cốt lõi của người lập trình.

Ví dụ, bài toán tính điểm trung bình của cả lớp nghe có vẻ to, nhưng chia nhỏ thì rất gọn: (1) đọc danh sách điểm từng học sinh; (2) cộng tất cả các điểm lại; (3) đếm số học sinh; (4) lấy tổng chia cho số lượng. Mỗi bước con đều đơn giản, và khi ghép lại ta có lời giải hoàn chỉnh.

Toàn bộ môn học này, từ vòng lặp, hàm, cho tới con trỏ và struct, đều là những công cụ giúp bạn diễn đạt và lắp ghép các bước nhỏ thành lời giải lớn. Nắm vững tư duy chia nhỏ ngay từ bây giờ sẽ giúp bạn đi xa.

Hai thuật toán kinh điển

Lý thuyết sẽ nhẹ nhàng hơn nhiều nếu ta nhìn hai bài toán mà mọi lập trình viên đều gặp: tìm kiếm và sắp xếp. Chúng đủ đơn giản để hiểu ngay, lại đủ giàu để minh hoạ mọi ý niệm quan trọng về thuật toán.

Tìm kiếm tuần tự

Bài toán: cho một dãy n số và một giá trị x, hãy cho biết x có trong dãy không, nếu có thì ở vị trí nào. Lời giải ngây thơ nhất cũng là lời giải đúng nhất về mặt tư duy khởi đầu: duyệt từ đầu tới cuối, so sánh từng phần tử với x, gặp là dừng.

#include <stdio.h>

// returns the index of x, or -1 if not found
int timTuanTu(const int a[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            return i;          // found: stop immediately
        }
    }
    return -1;                 // scanned everything, not found
}

int main(void) {
    int a[6] = {7, 3, 9, 1, 4, 8};
    printf("%d\n", timTuanTu(a, 6, 9));   // 2
    printf("%d\n", timTuanTu(a, 6, 5));   // -1
    return 0;
}

Hãy đọc đoạn mã này bằng lời, đó là kỹ năng cần rèn ngay từ bây giờ. Biến i lần lượt nhận các giá trị 0, 1, 2 cho tới n - 1, mỗi vòng ta so sánh phần tử thứ i với x. Nếu bằng thì return i kết thúc hàm ngay, không xét tiếp phần tử nào nữa. Nếu vòng lặp chạy hết mà chưa lần nào return thì toàn bộ dãy đã bị loại, và ta trả về -1 để báo "không có". Giá trị -1 được chọn vì nó không thể là một chỉ số hợp lệ, nên người gọi phân biệt được ngay giữa "tìm thấy ở vị trí 0" và "không tìm thấy". Đây là một mẹo thiết kế đáng nhớ: khi cần báo hiệu thất bại, hãy chọn một giá trị mà thành công không bao giờ có thể mang.

Thuật toán này tốn bao nhiêu phép so sánh? May mắn nhất, x nằm ngay đầu dãy, chỉ một phép. Xấu nhất, x nằm cuối hoặc không có, đúng n phép. Người ta luôn quan tâm trường hợp xấu nhất, vì đó là điều duy nhất ta dám hứa. Ta viết là O(n).

Sắp xếp chọn

Bài toán: sắp xếp dãy n số theo thứ tự tăng dần. Ý tưởng của sắp xếp chọn (selection sort) rất giống cách bạn xếp lại một cỗ bài trên tay: tìm quân nhỏ nhất trong phần chưa xếp, đưa nó về đầu, rồi lặp lại với phần còn lại.

#include <stdio.h>

void sapXepChon(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;                    // index of the smallest so far
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;                // found a smaller one
            }
        }
        if (min != i) {                 // swap only when needed
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

int main(void) {
    int a[6] = {7, 3, 9, 1, 4, 8};
    sapXepChon(a, 6);
    for (int i = 0; i < 6; i++) {
        printf("%d ", a[i]);            // 1 3 4 7 8 9
    }
    printf("\n");
    return 0;
}

Phân tích bằng lời để thấy rõ nó đúng. Sau vòng ngoài với i = 0, phần tử nhỏ nhất của cả dãy đã nằm ở vị trí 0. Sau vòng i = 1, phần tử nhỏ nhất trong phần còn lại nằm ở vị trí 1, và nó lớn hơn hoặc bằng phần tử ở vị trí 0. Cứ thế, sau vòng thứ i, đoạn từ 0 tới i chắc chắn đã sắp đúng và chứa toàn những giá trị nhỏ nhất. Đó gọi là bất biến vòng lặp (loop invariant): một mệnh đề luôn đúng sau mỗi vòng, và khi vòng lặp kết thúc nó chính là điều ta muốn chứng minh. Tập nhìn ra bất biến là cách chắc chắn nhất để tin rằng vòng lặp của mình đúng, chắc hơn nhiều so với chạy thử vài lần rồi thấy kết quả có vẻ ổn.

Cũng để ý vòng ngoài dừng ở i < n - 1 chứ không phải i < n: khi chỉ còn đúng một phần tử cuối chưa xét, nó tất nhiên đã ở đúng chỗ. Ranh giới của vòng lặp phải được lập luận, không phải đoán.

Vì sao độ phức tạp quan trọng

Sắp xếp chọn cần bao nhiêu phép so sánh? Vòng ngoài i = 0 kéo theo n - 1 phép so sánh ở vòng trong, i = 1 kéo theo n - 2 phép, và cứ giảm dần tới 1. Tổng cộng là (n - 1) + (n - 2) + ... + 1, tức n * (n - 1) / 2. Khi n lớn, con số này xấp xỉ một nửa của n bình phương, nên ta nói sắp xếp chọn có độ phức tạp O(n^2).

Ký hiệu O lớn không quan tâm hằng số, cũng không quan tâm những số hạng nhỏ. Nó chỉ trả lời một câu hỏi: khi dữ liệu phình to ra, khối lượng công việc phình theo kiểu nào? Đó mới là điều quyết định số phận của chương trình, chứ không phải chuyện máy bạn nhanh hay chậm. Hãy nhìn bảng sau, giả sử máy làm được 100 triệu phép cơ bản mỗi giây.

n	O(n) tốn khoảng	O(n^2) tốn khoảng
1 000	1 nghìn phép, tức thời	1 triệu phép, tức thời
100 000	100 nghìn phép, tức thời	10 tỉ phép, khoảng 100 giây
10 000 000	10 triệu phép, dưới 1 giây	100 nghìn tỉ phép, hơn 11 ngày

Bảng này giải thích vì sao người ta chịu khó học thuật toán. Khi n bằng 1000 thì hai cột chênh nhau không đáng kể, ai cũng có thể tưởng rằng thuật toán nào cũng như nhau. Nhưng dữ liệu thật ngoài đời không dừng ở 1000. Với 10 triệu bản ghi, một thuật toán O(n) chạy xong trước khi bạn kịp uống ngụm nước, còn một thuật toán O(n^2) chạy hết kỳ nghỉ hè. Mua máy nhanh gấp 10 lần cũng chỉ rút 11 ngày xuống hơn 1 ngày, trong khi đổi sang thuật toán tốt hơn thì rút xuống còn vài giây. Chọn đúng thuật toán ăn đứt việc tối ưu vặt hay nâng cấp phần cứng.

Cần nói cho công bằng về mặt trái. Với dữ liệu nhỏ, một thuật toán O(n^2) đơn giản có thể chạy nhanh hơn một thuật toán O(n log n) phức tạp, vì hằng số ẩn của nó bé hơn và lại dễ viết đúng hơn. Nguyên tắc thực dụng: viết cho đúng và dễ hiểu trước, chỉ tìm thuật toán tinh vi hơn khi dữ liệu thật sự lớn và bạn đã đo được rằng chỗ đó chậm.

Đọc ký hiệu O như thế nào

O(n) đọc là "tuyến tính": dữ liệu tăng gấp đôi thì thời gian tăng gấp đôi. O(n^2) đọc là "bậc hai": dữ liệu tăng gấp đôi thì thời gian tăng gấp bốn. O(log n) đọc là "lôgarit": dữ liệu tăng gấp đôi thì thời gian chỉ tăng thêm một chút. Cái ta so là dáng tăng, không phải con số cụ thể trên máy nào.

Kiểm thử và trường hợp biên

Một thuật toán chỉ đáng tin khi nó vẫn đúng ở những chỗ khó chịu nhất. Người mới thường thử với dữ liệu đẹp, thấy chạy ra kết quả đúng rồi kết luận là xong. Nhưng phần lớn lỗi trong thực tế không nằm ở dữ liệu đẹp, chúng nằm ở trường hợp biên (edge case), tức những đầu vào nằm ngay rìa của giả thiết.

Với bài tìm kiếm ở trên, danh sách trường hợp cần thử ít nhất gồm: dãy rỗng (n bằng 0), dãy chỉ có một phần tử, x nằm đầu, x nằm cuối, x không có trong dãy, và x xuất hiện nhiều lần. Với bài sắp xếp: dãy rỗng, dãy một phần tử, dãy đã sắp sẵn, dãy sắp ngược hoàn toàn, và dãy có nhiều phần tử trùng nhau. Hãy tự chạy timTuanTu và sapXepChon với từng trường hợp rồi đối chiếu kết quả với điều bạn mong đợi. Thói quen liệt kê trước, thử sau sẽ theo bạn suốt nghề.

Một mẹo kiểm thử rẻ mà hiệu quả là chạy tay: lấy một dãy ngắn chừng bốn năm phần tử, tự đóng vai máy tính, ghi ra giấy giá trị của từng biến sau mỗi vòng lặp. Cách này chậm, nhưng nó phơi bày những lỗi mà mắt nhìn code không thấy được, đặc biệt là lỗi lệch một đơn vị ở điều kiện dừng.

Ba lỗi thường gặp và nguyên nhân gốc

• Lỗi lệch một đơn vị (off by one): viết i <= n thay vì i < n khiến chương trình chạm vào a[n], một ô nằm ngoài mảng. Nguyên nhân gốc là nhầm lẫn giữa số lượng phần tử và chỉ số cuối cùng: mảng n phần tử có chỉ số hợp lệ từ 0 tới n - 1, không phải tới n.
• Vòng lặp không dừng: quên cập nhật biến điều khiển bên trong thân vòng, hoặc cập nhật theo hướng làm điều kiện dừng ngày càng xa. Nguyên nhân gốc là viết vòng lặp mà chưa chỉ ra được đại lượng nào đang tiến về điều kiện dừng.
• Không xử lý trường hợp rỗng: thuật toán tìm giá trị lớn nhất thường bắt đầu bằng "gán max bằng phần tử đầu tiên", nhưng khi dãy rỗng thì phần tử đầu tiên không tồn tại. Nguyên nhân gốc là ngầm giả định dữ liệu luôn có ít nhất một phần tử mà không hề ghi giả định đó ra.

Bài tập thực hành

Bài 1. Mô tả thuật toán kiểm tra một số nguyên n là chẵn hay lẻ bằng ba cách: liệt kê bước, lưu đồ và mã giả.

Gợi ý

Ý tưởng: lấy n chia 2 lấy phần dư; nếu phần dư bằng 0 thì chẵn, ngược lại lẻ. Liệt kê bước: (1) nhập n; (2) tính r bằng n chia lấy dư cho 2; (3) nếu r bằng 0 thì in chẵn, ngược lại in lẻ. Lưu đồ: khối nhập, một hình thoi hỏi r có bằng 0 không, hai nhánh đúng và sai dẫn tới hai khối xuất. Mã giả: Doc n rồi Neu n mod 2 = 0 thi Xuat "chan" Nguoc lai Xuat "le".

Bài 2. Vẽ (mô tả) lưu đồ cho thuật toán tìm số nhỏ nhất trong ba số a, b, c.

Gợi ý

Một cách: gán min bằng a, rồi dùng hai hình thoi liên tiếp. Hình thoi thứ nhất hỏi b có nhỏ hơn min không, nếu đúng thì gán min bằng b. Hình thoi thứ hai hỏi c có nhỏ hơn min không, nếu đúng thì gán min bằng c. Cuối cùng xuất min. Như vậy chỉ cần hai phép so sánh.

Bài 3. Viết mã giả cho thuật toán tính tổng các số nguyên từ 1 đến n, trong đó n là số nhập vào.

Gợi ý

Dùng một biến tích lũy và một vòng lặp:

Doc n
tong <- 0
i <- 1
Lap khi i <= n
    tong <- tong + i
    i <- i + 1
Het lap
Xuat tong

Có thể kiểm chứng nhanh bằng công thức n * (n + 1) / 2.

Bài 4. Liệt kê đầy đủ sáu bước xây dựng một chương trình và giải thích ngắn gọn vì sao không nên bỏ qua bước thiết kế thuật toán.

Gợi ý

Sáu bước: xác định bài toán, thiết kế thuật toán, viết chương trình, biên dịch và chạy thử, kiểm thử và sửa lỗi, bảo trì. Bỏ qua bước thiết kế khiến ta gõ code khi chưa có lời giải rõ ràng, dẫn tới code rối, nhiều lỗi logic và rất khó sửa về sau. Một phút phác thuật toán tiết kiệm nhiều giờ gỡ lỗi.

Bài 5. Viết hàm int demXuatHien(const int a[], int n, int x) đếm số lần giá trị x xuất hiện trong dãy. Hàm phải chạy đúng cả khi dãy rỗng. Cho biết độ phức tạp của nó.

Lời giải chi tiết

Bước 1: xác định bài toán. Dữ liệu vào là dãy a gồm n phần tử và giá trị x; kết quả ra là một số nguyên không âm. Nếu n bằng 0 thì kết quả đúng phải là 0, chứ không phải lỗi.

Bước 2: thiết kế thuật toán. Dùng một biến tích lũy dem khởi tạo bằng 0, duyệt toàn dãy, gặp phần tử bằng x thì tăng dem. Ở đây không được dừng sớm như tìm kiếm, vì ta cần đếm hết.

Bước 3: chú ý trường hợp biên. Vòng for với điều kiện i < n tự nhiên xử lý đúng dãy rỗng: khi n bằng 0, thân vòng không chạy lần nào và hàm trả về dem vẫn bằng 0. Đây là lý do nên viết i < n thay vì các biến thể dễ sai như i <= n - 1, vốn sẽ hỏng khi n bằng 0.

#include <stdio.h>

// counts how many times x appears in a[0..n-1]
int demXuatHien(const int a[], int n, int x) {
    int dem = 0;
    for (int i = 0; i < n; i++) {   // n == 0: loop body never runs, returns 0
        if (a[i] == x) {
            dem++;
        }
    }
    return dem;
}

int main(void) {
    int a[7] = {4, 1, 4, 9, 4, 2, 1};
    printf("%d\n", demXuatHien(a, 7, 4));   // 3
    printf("%d\n", demXuatHien(a, 7, 5));   // 0
    printf("%d\n", demXuatHien(a, 0, 4));   // 0, empty array
    return 0;
}

Độ phức tạp là O(n): hàm luôn duyệt đúng n phần tử, không hơn không kém, kể cả trong trường hợp tốt nhất lẫn xấu nhất.

Bài 6. Cho biết sắp xếp chọn trên dãy 5000 phần tử thực hiện khoảng bao nhiêu phép so sánh. Nếu dãy tăng lên 50000 phần tử thì số phép so sánh tăng gấp mấy lần?

Lời giải chi tiết

Số phép so sánh của sắp xếp chọn là n * (n - 1) / 2. Với n bằng 5000, ta có 5000 * 4999 / 2, xấp xỉ 12,5 triệu phép. Với n bằng 50000, ta có 50000 * 49999 / 2, xấp xỉ 1,25 tỉ phép.

Dữ liệu tăng 10 lần nhưng khối lượng công việc tăng khoảng 100 lần, tức bình phương của 10. Đó chính là ý nghĩa thực tế của O(n^2): dáng tăng bậc hai khiến chi phí bùng nổ nhanh hơn nhiều so với tốc độ phình của dữ liệu. Nếu bản chạy 5000 phần tử tốn 0,2 giây thì bản 50000 phần tử sẽ tốn khoảng 20 giây, còn 500000 phần tử sẽ tốn khoảng 2000 giây, tức hơn nửa giờ. Đây là lúc phải đổi thuật toán chứ không phải đổi máy.

Câu hỏi tự kiểm

Kiểm tra nhanh: thuật toán và độ phức tạp0/4 đúngchưa trả lời

1. 1Tính hữu hạn của một thuật toán nghĩa là gì?
2. 2Tìm kiếm tuần tự trên một dãy n phần tử, trường hợp xấu nhất tốn khoảng bao nhiêu phép so sánh?
3. 3Sắp xếp chọn (selection sort) có độ phức tạp thời gian trong ký hiệu O lớn là?
4. 4Viết nhầm điều kiện vòng lặp thành i <= n thay vì i < n khi duyệt mảng n phần tử gây ra lỗi gì?

Tóm tắt

Bài này đặt nền cho toàn bộ phần còn lại của môn học. Thuật toán là dãy hữu hạn các bước rõ ràng dẫn từ dữ liệu vào tới kết quả ra, và nó phải thoả bốn tính chất: xác định, hữu hạn, đúng đắn, có vào ra. Cái khó không nằm ở việc thuộc bốn tính chất đó mà ở việc thật sự áp dụng chúng khi tự soi lời giải của mình, bởi máy tính không lấp giúp ta bất kỳ khoảng trống nào.

Ta có ba cách mô tả bổ trợ nhau: liệt kê bước dễ đọc, lưu đồ trực quan nên hợp khi logic rối, mã giả gần code nên là cầu nối tự nhiên sang C. Quy trình sáu bước, từ xác định bài toán tới bảo trì, nhấn mạnh rằng gõ code chỉ là một mắt xích. Hai bước hay bị bỏ qua nhất, xác định bài toán và thiết kế thuật toán, lại là hai bước quyết định chất lượng của mọi thứ đến sau.

Qua tìm kiếm tuần tự và sắp xếp chọn, ta thấy ba ý niệm sẽ đi cùng bạn rất lâu: chọn một giá trị đặc biệt để báo hiệu thất bại, dùng bất biến vòng lặp để tin rằng vòng lặp của mình đúng, và dùng ký hiệu O để so sánh dáng tăng chứ không so sánh con số tuyệt đối. Cuối cùng, một thuật toán chỉ đáng tin sau khi đã được thử ở các trường hợp biên: dãy rỗng, dãy một phần tử, dữ liệu đã sắp, dữ liệu sắp ngược, dữ liệu trùng lặp.

Ghi nhớ

Thuật toán là dãy hữu hạn các bước rõ ràng để giải một bài toán, với bốn tính chất: xác định, hữu hạn, đúng đắn, có vào ra. Ta mô tả thuật toán bằng ba cách bổ trợ nhau: liệt kê bước (dễ đọc), lưu đồ (trực quan), mã giả (gần code). Xây dựng chương trình đi theo sáu bước, trong đó khâu thiết kế thuật toán quan trọng nhất và hay bị bỏ qua nhất. Cuối cùng, tư duy chia để trị giúp biến một bài toán lớn thành nhiều bài toán con đơn giản rồi ghép lại.