Đánh giá độ phức tạp thuật toán – Algorithmic complexity

Ở bài trước, mình đã giới thiệu hai giải thuật khá căn bản đó là tìm kiếm nhị phân và đệ quy. Trong bài viết, mình hay dùng cụm từ độ phức tạp của giải thuật này, độ phức tạp của giải thuật kia…, vậy O(n), O(logn) là gì và dựa vào đâu mà mình có thể khẳng định độ phức tạp của giải thuật này là O(n), độ phức tạp của giải thuật kia là O(logn)… Thì bài viết hôm nay mình sẽ giới thiệu về Big O và một vài nguyên tắc của Big O để đánh giá mức độ hiệu quả hay kém hiệu quả của một giải thuật.

Giới thiệu

Giải thuật đơn giản chỉ là cách để giải quyết vấn đề nào đó trong lập trình, việc đánh giá giải thuật chính là lựa chọn cách viết code (implement) sao cho hiệu quả nhất. Trong thực tế khi giải quyết vấn đề nào đó chúng ta cũng thường phân tích ưu nhược điểm các cách giải quyết để lựa chọn cách giải quyết có lợi hơn.

Ví dụ, khi mình cần di chuyển từ TP HCM về Bình Định, thông thường mình sẽ có 2 sự lựa chọn. Thứ nhất là đi bằng máy bay và thứ hai là đi bằng xe khách. Đi bằng máy bay có ưu điểm là sẽ nhanh nhưng nhược điểm là chi phí cao, và ngược lại đi bằng xe khách tuy chậm nhưng chi phí lại rẻ. Vậy thì mình đã dựa vào chi phí và thời gian để đánh giá là cách di chuyển nào là hiệu quả hơn. Do đó tùy vào trường hợp mình cần tiết kiệm khoản nào thì mà sử dụng phương tiện di chuyển cho hợp lý.

Tương tự trong lập trình, để giải quyết vấn đề nào đó thì chúng ta cũng cần sử dụng các phép tính toán hay còn gọi là độ phức tạp thời gian bởi và vùng nhớ để lưu trữ hay còn gọi là độ phức tạp không gian. Để đánh giá giải thuật này là hiệu quả hơn giải thuật khác ta cần phải đánh giá dựa trên cùng một tập dữ liệu và với kích thước dữ liệu là lớn (vì với tập dữ liệu nhỏ thì sẽ rất khó để đánh giá, vì tốc độ xử lý của máy tính là rất lớn). Tất nhiên cũng giống như trong ví dụ trên của mình, chúng ta cần tùy vào trường hợp để lựa chọn giải thuật phù hợp.

Phạm vi của bài viết này mình chỉ tổng hợp lại một vài thuật ngữ và quy tắc để đánh giá độ phức tạp về thời gian.

BigO

BigO là chỉ số để đánh giá độ phức tạp của một giải thuật được sử dụng phổ biến nhất trong lập trình (ngoài ra còn có Big Ô-mê-ga và Big Thê-ta).

BigO đánh giá dựa vào thời gian chạy lớn nhất của một giải thuật trên các dữ liệu cùng cỡ.

Ví dụ: Giải thuật tìm kiếm tuyến tính trong trường hợp tốt nhất chỉ cần thực hiện 1 phép tính, trường hợp xấu nhất là n phép tính và trường hợp trung bình là n/2 phép tính (với n là số lượng phần tử). Thì với BigO, độ phức tạp của giải thuật tìm kiếm tuyến tính là O(n).

Một số chỉ số độ phức tạp phổ biến theo mức độ tăng dần.
– Constant time: O(1) số phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào. vd: a + b
– Logarithmic time: O(logn) số phép tính (thời gian thực hiện) tăng theo kích thước dữ liệu theo hàm logarit. vd: tìm kiếm nhị phân
– Linear time: O(n) số phép tính phụ thuộc vào dữ liệu đầu vào theo 1 biến. vd: tìm kiếm tuyến tính
– Log-linear time: O(nlogn) tổng hợp của n và logn (lồng nhau). vd: Heap sort, Merge sort
– Polynimial time: O(n^c) các vòng lặp lồng nhau
– Exponential time: O(c^n)  bài toán tìm số fibonacci thứ n
– Factorial time: O(n!)  bài toán TSP

Biểu đồ thời gian với số lượng phần tử với các độ phức tạp

Đánh giá độ phức tạp

– Quy tắc hằng: O(k*f(n) = O(f(n)) đơn giản là ta bỏ hằng số đi. vd: O(100n) = O(n)
– Quy tắc cộng: O(f(n) + O(g(n)) = max(f(n),g(n), ta lấy độ phức tạp lớn hơn. vd: O(n^2 + n) = O(n^2)
– Quy tắc nhân: O(f(n) * O(g(n)) = O(f(n)) * O(g(n)) ta lấy tích. vd: O(n) * O(logn) = O(nlogn)

Bài tập:

int count = 0;
        for (int i = N; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                count += 1;
            }
        }

Các bạn hãy dựa vào nguyên tắc trên để đánh giá độ phức tạp của đoạn code trên nhé. Have fun!

Thuật toán đệ quy – Recursion algorithms

Chào mừng các bạn đã quay trở lại với thachleblog, ở bài trước mình đã giới thiệu với các bạn về thuật toán tìm kiếm nhị phân, hy vọng các bạn đã hiểu rõ và có thể tự tin áp dụng cho dự án của mình. Ở bài này, mình sẽ tiếp tục giới thiệu một thuật toán cơ bản khác đó chính là đệ quy. Lý do mình viết bài viết này là bởi vì thuật toán đệ quy rất căn bản, là tiền đề cho các thuật toán sau này như quick sort, merge sort, tree, graph… Mục tiêu bài viết này của mình là các bạn hiểu, nhận dạng và hiểu được ưu nhược điểm của thuật toán đệ quy. Nào, chúng ta cùng bắt đầu nhé.

Giới thiệu

Trước khi mình đi vào định nghĩa khá là ngắn gọn về khái niệm “đệ quy là gì” thì mình xin chia sẻ về một món đồ chơi mà mình thấy khá là thú vị.

Con búp bê bằng gỗ này được bán rất nhiều ở các khu hội chợ, các khu du lịch. Cấu tạo của nó rất đặc biệt, bên trong thân rỗng, chứa một con búp bê khác tương tự nhưng kích thước nhỏ hơn, và con tiếp theo cũng thế, cứ như vậy cho đến con nhỏ nhất (các bạn có thể mua về để rảnh rảnh vặn ra xếp như hình trên rồi lại xếp vào, cho bớt rảnh rỗi, hehe).

Tại sao mình lại nhắc đến cái con búp bê này, bởi vì cấu tạo của nó rất giống với thuật toán đệ quy. Bên trong con búp bê này chứa một con búp bê khác tương tự nó nhưng với kích thước nhỏ hơn và bên trong con nhỏ hơn đó cũng chứa một con nhỏ hơn khác, cho đến con nhỏ nhất (không chứa được thêm con nào). Bản thân thuật toán đệ quy chính là gọi lại chính nó với input nhỏ hơn (subproblem), cho đến điểm dừng (base case).

Ví dụ: tính giai thừa của số tự nhiên n

Thông thường, cách đơn giản nhất là dùng vòng lặp, chẳng cần quan tâm đệ quy là cái khỉ gì:

static int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

Tuy nhiên, chúng ta cũng có thể tính n giai thừa bằng đệ quy như sau:

static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

Để hiểu đệ quy chạy như thế nào thì các bạn hãy hình dung lại cấu trúc của con búp bê. Với đệ quy, bên trong method facotorial(n) sẽ gọi method factorial(n-1) và cứ thế đến factorial(0):

  • factorial(n) = n * factorial(n-1)

  • factorial(n-1)= n-1 * factorial(n-2)

  • ….

  • factorial(0) = 1;

Cấu trúc

Nhìn vào ví dụ trên chúng ta có thể thấy đệ quy thường gồm 2 phần:

  • Base case: điểm mà vấn đề đã được chia đến mức nhỏ nhất và đã có thể dừng lại (factorial(0))

  • Recursion case: phần gọi lại chính nó với input nhỏ hơn. Cho đến khi gặp base case

So sánh với vòng lặp

Từ ví dụ trên, ta có thể nhận thấy thuật toán đệ quy sẽ tốn nhiều bộ nhớ hơn so với dùng vòng lặp, vì method được gọi lại nhiều lần, mỗi lần gọi method sẽ được lưu vào vùng nhớ stack cho đến basecase. Do đó, theo mình, trong các trường hợp thông thường, nếu có thể dùng vòng lặp thì hãy dùng vòng lặp, chẳng nên “làm màu” làm gì, hehe.

Tuy nhiên, thuật toán đệ quy lại cực kỳ hiệu quả và tường minh trong các bài toán duyệt trees, grapth… mà có thể mình sẽ giới thiệu ở các phần sau.

Tìm kiếm nhị phân bằng đệ quy

Mỗi bài toán được viết bằng đệ quy thì có thể chuyển sang dùng vòng lặp và ngược lại. Ở bài trước, mình đã viết thuật toán tìm kiếm nhị phân (binary search) bằng vòng lặp while, hôm nay mình sẽ tiếp cận bằng thuật toán đệ quy.

Giải thuật rất đơn giản, sau khi chọn điểm chính giữa mảng và so sánh với giá trị cần tìm, ta sẽ chia mảng thành 2 phần. Sau khi xác định giá trị cần tìm ở phần nào ta lại tiếp chọn lại điểm chính giữa của mảng con đó và và so sánh … Rõ ràng cách tiếp cận này cho ta cái nhìn rõ ràng hơn về khái niệm “nhị phân” tức là chia làm đôi.

int binarySearch(int arr[], int l, int r, int x) {
        if (r >= l) {
            int mid = l + (r - l) / 2;
 
            // If the element is present at the 
            // middle itself
            if (arr[mid] == x) {
                return mid;
            }
 
            // If element is smaller than mid, then 
            // it can only be present in left subarray
            if (arr[mid] > x) {
                return binarySearch(arr, l, mid - 1, x);
            }
 
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid + 1, r, x);
        }
 
        // We reach here when element is not present
        //  in array
        return -1;
 
    }

(nguồn source code geeksforgeeks)

Kết

Tạm kết ở đây, thực ra kiến thức này đã được học từ năm 1, năm 2 đại học, tiếc là hồi đó mình ngơ ngơ chả biết gì, chỉ học qua loa, hậu quả là ra trường thỉnh thoảng đọc code chả biết nó là cái gì -.-. Hy vọng qua bài viết này giúp các bạn đã từng mất gốc như mình hiểu được đệ quy và qua đó hiểu được cơ chế của các thuật toán sử dụng đệ quy như quick sort, merge sort hoặc các cấu trúc duyệt trees, grapth…. Mình rất mong nhận được góp ý của các bạn để hoàn thiện bài viết hơn về cách trình bày, nội dung… Cảm ơn và hẹn gặp lại các bạn ở các bài viết sau

Link tham khảo thêm:

https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion

https://www.geeksforgeeks.org/binary-search/