Week 3 Thuật toán

Chào mừng các bạn!

Trong tuần 0, chúng ta đã làm quen với khái niệm thuật toán (algorithm): một chiếc hộp đen có thể nhận đầu vào và tạo ra đầu ra.
Tuần này, chúng ta sẽ mở rộng hiểu biết về thuật toán thông qua mã giả và chuyển đổi chúng thành mã nguồn thực tế.
Ngoài ra, chúng ta cũng sẽ xem xét hiệu suất của các thuật toán này. Thực tế, chúng ta sẽ xây dựng dựa trên hiểu biết về cách sử dụng một số khái niệm đã thảo luận tuần trước để xây dựng các thuật toán.

Hãy nhớ lại phần đầu của khóa học khi chúng ta giới thiệu biểu đồ sau:

Khi bước vào tuần này, bạn nên cân nhắc xem cách một thuật toán xử lý vấn đề sẽ quyết định thời gian cần thiết để giải quyết vấn đề đó như thế nào! Các thuật toán có thể được thiết kế để ngày càng hiệu quả hơn cho đến một giới hạn nhất định.
Hôm nay, chúng ta sẽ tập trung vào việc thiết kế các thuật toán và cách đo lường hiệu suất của chúng.

Tìm kiếm tuyến tính (Linear Search)

Hãy nhớ lại rằng tuần trước, bạn đã được giới thiệu về khái niệm mảng (array), các khối bộ nhớ liên tiếp nhau: nằm cạnh nhau.

Bạn có thể hình dung một mảng giống như một dãy bảy chiếc tủ khóa màu đỏ như sau:

Vị trí ngoài cùng bên trái được gọi là vị trí 0 hoặc điểm đầu của mảng. Vị trí ngoài cùng bên phải là vị trí 6 hoặc điểm cuối của mảng.
Chúng ta có thể giả định một vấn đề cơ bản là muốn biết: “Số 50 có nằm trong mảng không?” Máy tính phải kiểm tra từng chiếc tủ để xem số 50 có bên trong hay không. Chúng ta gọi quá trình tìm kiếm một con số, ký tự, chuỗi hoặc mục khác như vậy là searching (tìm kiếm).

Chúng ta có thể đưa mảng của mình cho một thuật toán, trong đó thuật toán sẽ tìm kiếm qua các tủ khóa để xem số 50 có nằm sau một trong những cánh cửa hay không, và trả về giá trị true (đúng) hoặc false (sai).

Chúng ta có thể hình dung các chỉ dẫn khác nhau mà chúng ta có thể cung cấp cho thuật toán để thực hiện nhiệm vụ này như sau:

For each door from left to right
    If 50 is behind door
        Return true
Return false

Lưu ý rằng các chỉ dẫn trên được gọi là mã giả (pseudocode): Một phiên bản ngôn ngữ tự nhiên của các chỉ dẫn mà chúng ta có thể cung cấp cho máy tính.

Một nhà khoa học máy tính có thể dịch mã giả đó như sau:

For i from 0 to n-1
    If 50 is behind doors[i]
        Return true
Return false

Lưu ý rằng đoạn trên vẫn chưa phải là mã nguồn, nhưng nó là một bản mô phỏng khá gần với hình dáng của mã nguồn cuối cùng.

Tìm kiếm nhị phân (Binary Search)

Tìm kiếm nhị phân (Binary search) là một thuật toán tìm kiếm khác có thể được sử dụng trong nhiệm vụ tìm số 50.

Giả sử rằng các giá trị trong các tủ khóa đã được sắp xếp từ nhỏ đến lớn, mã giả cho tìm kiếm nhị phân sẽ như sau:

If no doors left
    Return false
If 50 is behind middle door
    Return true
Else if 50 < middle door
    Search left half
Else if 50 > middle door
    Search right half

Sử dụng quy ước của mã nguồn, chúng ta có thể sửa đổi thêm thuật toán của mình như sau:

If no doors left
    Return false
If 50 is behind doors[middle]
    Return true
Else if 50 < doors[middle]
    Search doors[0] through doors[middle - 1]
Else if 50 > doors[middle]
    Search doors[middle + 1] through doors[n - 1]

Lưu ý rằng bằng cách nhìn vào bản mô phỏng mã này, bạn gần như có thể hình dung nó sẽ trông như thế nào trong mã nguồn thực tế.

Thời gian chạy (Running Time)

Bạn có thể xem xét thuật toán mất bao nhiêu thời gian để giải quyết một vấn đề.

Thời gian chạy (running time) bao gồm việc phân tích bằng ký hiệu O lớn (big O). Hãy nhìn vào biểu đồ sau:

Thay vì quá chi tiết về hiệu suất toán học của một thuật toán, các nhà khoa học máy tính thảo luận về hiệu suất theo độ lớn của các thời gian chạy khác nhau.
Trong biểu đồ trên, thuật toán đầu tiên là \(O(n)\) hoặc độ lớn n. Thuật toán thứ hai cũng là \(O(n)\). Thuật toán thứ ba là \(O(\log n)\).

Chính hình dạng của đường cong cho thấy hiệu suất của một thuật toán. Một số thời gian chạy phổ biến mà chúng ta có thể thấy là:

\(O(n^2)\)
\(O(n \log n)\)
\(O(n)\)
\(O(\log n)\)
\(O(1)\)
Trong các thời gian chạy ở trên, \(O(n^2)\) được coi là thời gian chạy chậm nhất. \(O(1)\) là nhanh nhất.
Tìm kiếm tuyến tính có độ lớn \(O(n)\) vì nó có thể mất n bước trong trường hợp xấu nhất để chạy.
Tìm kiếm nhị phân có độ lớn \(O(\log n)\) vì nó sẽ mất ngày càng ít bước hơn để chạy, ngay cả trong trường hợp xấu nhất.
Các lập trình viên quan tâm đến cả trường hợp xấu nhất, hay cận trên (upper bound), và trường hợp tốt nhất, hay cận dưới (lower bound).
Ký hiệu \(\Omega\) được sử dụng để biểu thị trường hợp tốt nhất của một thuật toán, chẳng hạn như \(\Omega(\log n)\).
Ký hiệu \(\Theta\) được sử dụng để biểu thị khi cận trên và cận dưới giống nhau: Nơi thời gian chạy tốt nhất và xấu nhất là như nhau.

Ký hiệu tiệm cận (Asymptotic notation) là thước đo mức độ hoạt động của các thuật toán khi đầu vào ngày càng lớn.

Khi bạn tiếp tục phát triển kiến thức về khoa học máy tính, bạn sẽ khám phá các chủ đề này chi tiết hơn trong các khóa học tương lai.

search.c

Bạn có thể triển khai tìm kiếm tuyến tính bằng cách nhập code search.c vào cửa sổ terminal và viết mã như sau:

// Implements linear search for integers

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // An array of integers
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Search for number
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Lưu ý rằng dòng bắt đầu bằng int numbers[] cho phép chúng ta xác định giá trị của từng phần tử trong mảng ngay khi tạo ra nó. Sau đó, trong vòng lặp for, chúng ta có một bản triển khai của tìm kiếm tuyến tính. return 0 được sử dụng để báo hiệu thành công và thoát chương trình. return 1 được sử dụng để thoát chương trình với một lỗi (thất bại).

Bây giờ chúng ta đã tự mình triển khai tìm kiếm tuyến tính trong C!

Nếu chúng ta muốn tìm kiếm một chuỗi (string) trong một mảng thì sao? Hãy sửa đổi mã của bạn như sau:

// Implements linear search for strings

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // An array of strings
    string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"};

    // Search for string
    string s = get_string("String: ");
    for (int i = 0; i < 6; i++)
    {
        if (strcmp(strings[i], s) == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Lưu ý rằng chúng ta không thể sử dụng == như trong phiên bản trước của chương trình này. Thay vào đó, chúng ta sử dụng strcmp, hàm này đến từ thư viện string.h. strcmp sẽ trả về 0 nếu các chuỗi giống nhau. Ngoài ra, hãy lưu ý rằng độ dài chuỗi là 6 được mã hóa cứng (hard-coded), điều này không phải là thói quen lập trình tốt.

Thực tế, việc chạy mã này cho phép chúng ta lặp qua mảng chuỗi này để xem một chuỗi nhất định có nằm trong đó hay không. Tuy nhiên, nếu bạn thấy lỗi segmentation fault, nơi chương trình của bạn chạm vào một phần bộ nhớ mà nó không có quyền truy cập, hãy đảm bảo bạn đã ghi i < 6 ở trên thay vì i < 7.
Bạn có thể tìm hiểu thêm về strcmp tại Trang hướng dẫn của CS50.

phonebook.c

Chúng ta có thể kết hợp các ý tưởng về cả số và chuỗi vào một chương trình duy nhất. Nhập code phonebook.c vào cửa sổ terminal và viết mã như sau:

// Implements a phone book without structs

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // Arrays of strings
    string names[] = {"Yuliia", "David", "John"};
    string numbers[] = {"+1-617-495-1000", "+1-617-495-1000", "+1-949-468-2750"};

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(names[i], name) == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Lưu ý rằng số của Yuliia bắt đầu bằng +1-617, số điện thoại của David bắt đầu bằng +1-617 và số của John bắt đầu bằng +1-949. Do đó, names[0] là Yuliia, và numbers[0] là số của Yuliia. Mã này sẽ cho phép chúng ta tìm kiếm trong danh bạ số điện thoại cụ thể của một người.

Mặc dù mã này hoạt động, nhưng có rất nhiều điểm không hiệu quả. Thực tế, có khả năng tên và số điện thoại không tương ứng với nhau. Sẽ thật tốt nếu chúng ta có thể tạo kiểu dữ liệu của riêng mình để liên kết một người với số điện thoại của họ?

Struct (Kiểu cấu trúc)

Hóa ra C cho phép chúng ta tạo kiểu dữ liệu của riêng mình thông qua một struct.

Sẽ thật hữu ích nếu chúng ta tạo một kiểu dữ liệu riêng gọi là person có chứa bên trong nó name (tên) và number (số điện thoại)? Hãy xem xét ví dụ sau:

typedef struct
{
    string name;
    string number;
} person;

Lưu ý cách này đại diện cho kiểu dữ liệu của riêng chúng ta có tên là person có một chuỗi tên là name và một chuỗi khác tên là number.

Chúng ta có thể cải thiện mã trước đó bằng cách sửa đổi chương trình danh bạ của mình như sau:

// Implements a phone book with structs

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
    string name;
    string number;
} person;

int main(void)
{
    person people[3];

    people[0].name = "Yuliia";
    people[0].number = "+1-617-495-1000";

    people[1].name = "David";
    people[1].number = "+1-617-495-1000";

    people[2].name = "John";
    people[2].number = "+1-949-468-2750";

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(people[i].name, name) == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Lưu ý rằng mã bắt đầu bằng typedef struct nơi một kiểu dữ liệu mới gọi là person được định nghĩa. Bên trong một person là một chuỗi tên là name và một string tên là number. Trong hàm main, bắt đầu bằng việc tạo một mảng tên là people có kiểu person với kích thước là 3. Sau đó, chúng ta cập nhật tên và số điện thoại của các cá nhân trong mảng people. Quan trọng nhất, hãy lưu ý cách ký hiệu dấu chấm (dot notation), chẳng hạn như people[0].name, cho phép chúng ta truy cập person ở vị trí thứ 0 và gán tên cho cá nhân đó.

Sắp xếp (Sorting)

Sắp xếp (Sorting) là hành động lấy một danh sách các giá trị chưa được sắp xếp và chuyển đổi danh sách này thành một danh sách đã được sắp xếp.

Khi một danh sách đã được sắp xếp, việc tìm kiếm trong danh sách đó sẽ ít tốn kém hơn nhiều đối với máy tính. Hãy nhớ rằng chúng ta có thể sử dụng tìm kiếm nhị phân trên một danh sách đã sắp xếp nhưng không thể sử dụng trên một danh sách chưa sắp xếp.
Hóa ra có nhiều loại thuật toán sắp xếp khác nhau.

Sắp xếp chọn (Selection sort) là một thuật toán sắp xếp như vậy.

Chúng ta có thể biểu diễn một mảng như sau:

Thuật toán sắp xếp chọn trong mã giả là:

For i from 0 to n–1
    Find smallest number between numbers[i] and numbers[n-1]
    Swap smallest number with numbers[i]

Tóm tắt các bước đó, lần lặp đầu tiên qua danh sách mất n - 1 bước. Lần thứ hai, mất n - 2 bước. Tiếp tục logic này, các bước cần thiết có thể được biểu diễn như sau:

(n - 1) + (n - 2) + (n - 3) + ... + 1

Điều này có thể được đơn giản hóa thành n(n-1)/2 hoặc, đơn giản hơn là \(O(n^2)\). Trong trường hợp xấu nhất hoặc cận trên, sắp xếp chọn có độ lớn \(O(n^2)\). Trong trường hợp tốt nhất, hoặc cận dưới, sắp xếp chọn có độ lớn \(\Omega(n^2)\).

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp nổi bọt (Bubble sort) là một thuật toán sắp xếp khác hoạt động bằng cách hoán đổi các phần tử lặp đi lặp lại để các phần tử lớn hơn “nổi” về phía cuối.

Mã giả cho sắp xếp nổi bọt là:

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them
    If no swaps
        Quit

Khi chúng ta sắp xếp thêm mảng, chúng ta biết rằng ngày càng nhiều phần của nó được sắp xếp, vì vậy chúng ta chỉ cần nhìn vào các cặp số chưa được sắp xếp.

Sắp xếp nổi bọt có thể được phân tích như sau:

  (n – 1) × (n – 1)
  n2 – 1n – 1n + 1
  n2 – 2n + 1

hoặc đơn giản hơn là \(O(n^2)\).

Trong trường hợp xấu nhất, hoặc cận trên, sắp xếp nổi bọt có độ lớn \(O(n^2)\). Trong trường hợp tốt nhất, hoặc cận dưới, sắp xếp nổi bọt có độ lớn \(\Omega(n)\).
Bạn có thể trực quan hóa một phép so sánh các thuật toán này.

Đệ quy (Recursion)

Làm thế nào chúng ta có thể cải thiện hiệu suất sắp xếp của mình?

Đệ quy (Recursion) là một khái niệm trong lập trình, nơi một hàm tự gọi chính nó. Chúng ta đã thấy điều này trước đây khi thấy…

If no doors left
    Return false
If number behind middle door
    Return true
Else if number < middle door
    Search left half
Else if number > middle door
    Search right half

Lưu ý rằng chúng ta đang gọi search trên các lần lặp ngày càng nhỏ hơn của vấn đề này.

Tương tự, trong mã giả của chúng ta cho Tuần 0, bạn có thể thấy nơi đệ quy đã được triển khai:

1  Nhấc cuốn danh bạ điện thoại
2  Mở đến giữa cuốn danh bạ
3  Nhìn vào trang
4  Nếu người đó có trên trang
5      Gọi người đó
6  Nếu không, nếu người đó ở phần trước của cuốn sách
7      Mở đến giữa nửa bên trái của cuốn sách
8      Quay lại dòng 3
9  Nếu không, nếu người đó ở phần sau của cuốn sách
10     Mở đến giữa nửa bên phải của cuốn sách
11     Quay lại dòng 3
12 Nếu không
13     Thoát

Mã này có thể đã được đơn giản hóa để làm nổi bật các đặc tính đệ quy của nó như sau:

1  Nhấc cuốn danh bạ điện thoại
2  Mở đến giữa cuốn danh bạ
3  Nhìn vào trang
4  Nếu người đó có trên trang
5      Gọi người đó
6  Nếu không, nếu người đó ở phần trước của cuốn sách
7      Tìm kiếm nửa bên trái của cuốn sách
9  Nếu không, nếu người đó ở phần sau của cuốn sách
10     Tìm kiếm nửa bên phải của cuốn sách
12 Nếu không
13     Thoát

Hãy xem xét cách trong Tuần 1 chúng ta muốn tạo một cấu trúc kim tự tháp như sau:

  #
  ##
  ###
  ####

Nhập code iteration.c vào cửa sổ terminal và viết mã như sau:

// Draws a pyramid using iteration

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // Draw pyramid of height n
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

Lưu ý rằng mã này xây dựng kim tự tháp bằng cách sử dụng các vòng lặp.

Để triển khai điều này bằng đệ quy, hãy nhập code iteration.c vào cửa sổ terminal và viết mã như sau:

// Draws a pyramid using recursion

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // If nothing to draw
    if (n <= 0)
    {
        return;
    }

    // Draw pyramid of height n - 1
    draw(n - 1);

    // Draw one more row of width n
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

Lưu ý trường hợp cơ sở (base case) sẽ đảm bảo mã không chạy mãi mãi. Dòng if (n <= 0) kết thúc đệ quy vì vấn đề đã được giải quyết. Mỗi khi draw tự gọi chính nó, nó sẽ gọi với giá trị n-1. Tại một thời điểm nào đó, n-1 sẽ bằng 0, dẫn đến hàm draw trả về và chương trình sẽ kết thúc.

Sắp xếp trộn (Merge Sort)

Bây giờ chúng ta có thể tận dụng đệ quy trong hành trình tìm kiếm một thuật toán sắp xếp hiệu quả hơn và triển khai cái được gọi là sắp xếp trộn (merge sort), một thuật toán sắp xếp rất hiệu quả.

Mã giả cho sắp xếp trộn khá ngắn:

If only one number
    Quit
Else
    Sort left half of numbers
    Sort right half of numbers
    Merge sorted halves

Hãy xem xét danh sách các con số sau:

  6 3 4 1

Đầu tiên, sắp xếp trộn hỏi, “đây có phải là một con số không?” Câu trả lời là “không”, vì vậy thuật toán tiếp tục.

  6 3 4 1

Thứ hai, sắp xếp trộn bây giờ sẽ chia các con số ở giữa (hoặc gần nhất có thể) và sắp xếp nửa bên trái của các con số.

  6 3 | 4 1

Thứ ba, sắp xếp trộn sẽ nhìn vào những con số bên trái này và hỏi, “đây có phải là một con số không?” Vì câu trả lời là không, nên sau đó nó sẽ chia các con số bên trái ở giữa.

  6 | 3

Thứ tư, sắp xếp trộn sẽ lại hỏi, “đây có phải là một con số không?” Câu trả lời là có lần này! Do đó, nó sẽ thoát khỏi nhiệm vụ này và quay lại nhiệm vụ cuối cùng mà nó đang chạy tại thời điểm này:

  6 3 | 4 1

Thứ năm, sắp xếp trộn sẽ sắp xếp các con số bên trái.

  3 6 | 4 1

Bây giờ, chúng ta quay lại nơi chúng ta đã dừng lại trong mã giả sau khi phía bên trái đã được sắp xếp. Một quá trình tương tự từ bước 3-5 sẽ xảy ra với các con số bên phải. Điều này sẽ dẫn đến:

  3 6 | 1 4

Cả hai nửa bây giờ đã được sắp xếp. Cuối cùng, thuật toán sẽ trộn cả hai phía. Nó sẽ nhìn vào con số đầu tiên bên trái và con số đầu tiên bên phải. Nó sẽ đặt số nhỏ hơn lên trước, sau đó là số nhỏ thứ hai. Thuật toán sẽ lặp lại điều này cho tất cả các số, dẫn đến:

  1 3 4 6

Sắp xếp trộn hoàn tất và chương trình kết thúc.
Sắp xếp trộn là một thuật toán sắp xếp rất hiệu quả với trường hợp xấu nhất là \(O(n \log n)\). Trường hợp tốt nhất vẫn là \(\Omega(n \log n)\) vì thuật toán vẫn phải truy cập từng vị trí trong danh sách. Do đó, sắp xếp trộn cũng là \(\Theta(n \log n)\) vì trường hợp tốt nhất và xấu nhất là như nhau.
Một đoạn phim trực quan hóa cuối cùng đã được chia sẻ.

Tổng kết

Trong bài học này, bạn đã tìm hiểu về tư duy thuật toán và xây dựng các kiểu dữ liệu của riêng mình. Cụ thể, bạn đã học…

Các thuật toán (Algorithms).
Ký hiệu O lớn (Big O notation).
Tìm kiếm nhị phân và tìm kiếm tuyến tính.
Các thuật toán sắp xếp khác nhau, bao gồm sắp xếp nổi bọt (bubble sort), sắp xếp chọn (selection sort) và sắp xếp trộn (merge sort).
Đệ quy (Recursion).

Hẹn gặp lại bạn vào lần tới!