Bài 1.4. Phương pháp phân tích và đánh giá hiệu suất thuật toán

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật (CTDL & GT)! Ở các bài trước, chúng ta đã làm quen với khái niệm cơ bản về CTDL và GT. Hôm nay, chúng ta sẽ đi sâu vào một chủ đề cực kỳ quan trọng, đó là cách phân tích và đánh giá hiệu suất của một thuật toán. Viết ra một đoạn code chạy được là tốt, nhưng viết ra một đoạn code chạy hiệu quả còn tốt hơn nhiều!

Tại sao phải phân tích hiệu suất thuật toán?

Bạn đã bao giờ tự hỏi tại sao cùng giải quyết một bài toán (ví dụ: sắp xếp một danh sách), có thuật toán chạy "nhanh như chớp" với dữ liệu lớn, trong khi thuật toán khác lại "ì ạch" đến đáng sợ không? Sự khác biệt đó chính là ở hiệu suất của thuật toán.

Việc phân tích hiệu suất thuật toán giúp chúng ta:

Dự đoán hành vi: Chúng ta có thể dự đoán thuật toán sẽ hoạt động như thế nào khi kích thước dữ liệu đầu vào (thường ký hiệu là n) trở nên rất lớn, mà không cần phải chạy thử trên dữ liệu thật.
So sánh các thuật toán: Khi có nhiều thuật toán cùng giải quyết một vấn đề, phân tích giúp chúng ta xác định thuật toán nào là tối ưu nhất về mặt thời gian hoặc bộ nhớ sử dụng.
Hiểu rõ giới hạn: Chúng ta biết được thuật toán của mình có thể xử lý dữ liệu đến kích thước nào trong một khoảng thời gian chấp nhận được.
Tối ưu hóa: Phân tích thường chỉ ra "nút cổ chai" (bottleneck) trong thuật toán, nơi tiêu tốn nhiều tài nguyên nhất, từ đó chúng ta biết cần tập trung vào đâu để cải thiện.

Nói tóm lại, phân tích hiệu suất là trái tim của việc thiết kế thuật toán hiệu quả.

Các phương pháp phân tích hiệu suất

Có hai phương pháp chính để phân tích hiệu suất thuật toán:

Phân tích thực nghiệm (Empirical Analysis): Chạy thuật toán trên các bộ dữ liệu đầu vào khác nhau và đo đạc thời gian thực thi, lượng bộ nhớ sử dụng.
- Ưu điểm: Cho kết quả chính xác trên môi trường thực tế.
- Nhược điểm:
  - Phụ thuộc vào phần cứng, hệ điều hành, ngôn ngữ lập trình, trình biên dịch.
  - Kết quả chỉ đúng với các bộ dữ liệu đã thử nghiệm.
  - Tốn thời gian để cài đặt và chạy thử.
  - Không dễ để dự đoán hành vi với dữ liệu rất lớn nếu chưa chạy thử.
Phân tích lý thuyết (Theoretical Analysis): Phân tích thuật toán bằng cách đếm số lượng các thao tác cơ bản mà thuật toán thực hiện, dựa trên kích thước dữ liệu đầu vào n. Phương pháp này thường bỏ qua các yếu tố phụ thuộc môi trường và tập trung vào tốc độ tăng trưởng của số thao tác khi n tăng lên.
- Ưu điểm:
  - Độc lập với phần cứng, ngôn ngữ lập trình.
  - Cho kết quả tổng quát về hành vi của thuật toán khi n lớn.
  - Có thể thực hiện trước khi viết code.
- Nhược điểm: Thường bỏ qua các hằng số và các thành phần bậc thấp, có thể không hoàn toàn phản ánh hiệu suất thực tế với dữ liệu nhỏ.

Trong khuôn khổ bài viết này và trong CTDL & GT nói chung, chúng ta sẽ tập trung chủ yếu vào phân tích lý thuyết, đặc biệt là phân tích tiệm cận (asymptotic analysis) sử dụng Ký hiệu Big O (Big O Notation).

Phân tích Tiệm cận và Ký hiệu Big O

Khi n (kích thước đầu vào) trở nên rất lớn, các hằng số và các thành phần bậc thấp trong biểu thức đếm số thao tác trở nên không đáng kể so với thành phần có bậc cao nhất. Phân tích tiệm cận tập trung vào tốc độ tăng trưởng của thuật toán khi n tiến tới vô cùng.

Ký hiệu Big O (O) là ký hiệu phổ biến nhất trong phân tích tiệm cận. Nó dùng để mô tả cận trên (upper bound) của tốc độ tăng trưởng số thao tác của thuật toán. Một cách không chính thức, Big O cho biết "tối đa" thuật toán sẽ chậm đến mức nào khi n lớn.

Chúng ta nói rằng hàm f(n) là O(g(n)) nếu tồn tại các hằng số dương c và n₀ sao cho f(n) ≤ c * g(n) với mọi n ≥ n₀. Ở đây, f(n) là số thao tác thực tế của thuật toán, và g(n) là một hàm đơn giản mô tả tốc độ tăng trưởng (ví dụ: n, n², log n).

Mục tiêu của việc sử dụng Big O là để đơn giản hóa biểu thức đếm thao tác, chỉ giữ lại thành phần có tốc độ tăng trưởng nhanh nhất và bỏ qua các hằng số.

Ví dụ đơn giản: Nếu một thuật toán thực hiện 5n² + 3n + 10 thao tác. Khi n rất lớn:

n² tăng trưởng nhanh hơn 3n.
3n tăng trưởng nhanh hơn 10.
Hằng số 5 nhân với n² chỉ làm thay đổi độ dốc, không thay đổi bản chất tốc độ tăng trưởng là theo bậc n².

Do đó, chúng ta nói thuật toán này có độ phức tạp thời gian là O(n²).

Các độ phức tạp thời gian phổ biến

Đây là một số ký hiệu Big O thường gặp, sắp xếp từ nhanh nhất (hiệu quả nhất) đến chậm nhất (kém hiệu quả nhất) khi n lớn:

O(1) - Độ phức tạp hằng số: Số thao tác không phụ thuộc vào kích thước đầu vào n.
O(log n) - Độ phức tạp Logarit: Số thao tác tăng rất chậm khi n tăng. Thường xuất hiện trong các thuật toán chia để trị (ví dụ: tìm kiếm nhị phân).
O(n) - Độ phức tạp Tuyến tính: Số thao tác tăng tỷ lệ thuận với n. Thường xuất hiện trong các vòng lặp đơn giản lặp qua tất cả các phần tử.
O(n log n) - Độ phức tạp Tuyến tính-Logarit: Tốt hơn O(n²) nhưng chậm hơn O(n). Thường xuất hiện trong các thuật toán sắp xếp hiệu quả (ví dụ: Merge Sort, Quick Sort).
O(n²) - Độ phức tạp Bình phương: Số thao tác tăng theo bình phương của n. Thường xuất hiện trong các vòng lặp lồng nhau.
O(2ⁿ) - Độ phức tạp Mũ: Số thao tác tăng theo cấp số mũ của n. Cực kỳ chậm, chỉ phù hợp với n rất nhỏ.
O(n!) - Độ phức tạp Giai thừa: Số thao tác tăng theo giai thừa của n. Chậm nhất, chỉ dùng cho n cực nhỏ.

Cách phân tích độ phức tạp thời gian bằng cách đếm thao tác

Chúng ta sẽ xem xét các cấu trúc lập trình cơ bản và cách phân tích chúng.

1. Các phép gán, phép toán số học, truy cập mảng/biến đơn giản

int a = 5;
int b = a + 10;
arr[i] = b;

Các thao tác này thường được coi là mất một khoảng thời gian hằng số. Bất kể n lớn hay nhỏ, thời gian thực hiện chúng là cố định (hoặc thay đổi không đáng kể). Độ phức tạp: O(1).

2. Vòng lặp đơn

void processArray(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        // Thao tác O(1) bên trong vòng lặp
        int temp = arr[i] * 2;
        std::cout << temp << std::endl;
    }
}

Giải thích: Vòng lặp for chạy từ i = 0 đến n-1, tức là lặp lại n lần. Bên trong mỗi lần lặp, các thao tác (nhân, gán, in) đều có độ phức tạp O(1). Tổng số thao tác sẽ là n * O(1) = O(n). Độ phức tạp thời gian: O(n).

3. Vòng lặp lồng nhau

void processPairs(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // Thao tác O(1) bên trong vòng lặp lồng nhau
            if (arr[i] > arr[j]) {
                // ...
            }
        }
    }
}

Giải thích: Vòng lặp ngoài chạy n lần. Với mỗi lần lặp của vòng lặp ngoài, vòng lặp trong cũng chạy n lần. Tổng số lần thực hiện các thao tác bên trong vòng lặp lồng nhau là n * n = n². Độ phức tạp thời gian: O(n²).

Ví dụ vòng lặp lồng nhau với số lần lặp khác nhau:

void processTriangle(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            // Thao tác O(1)
            std::cout << arr[i] << ", " << arr[j] << std::endl;
        }
    }
}

Giải thích:

Khi i = 0, vòng lặp trong chạy n lần (j từ 0 đến n-1).
Khi i = 1, vòng lặp trong chạy n-1 lần (j từ 1 đến n-1).
...
Khi i = n-1, vòng lặp trong chạy 1 lần (j từ n-1 đến n-1). Tổng số thao tác O(1) là: n + (n-1) + (n-2) + ... + 1. Đây là tổng của một cấp số cộng, có công thức là n * (n+1) / 2. Biểu thức số thao tác là (n² + n) / 2 = 0.5n² + 0.5n. Khi n lớn, thành phần 0.5n² chiếm ưu thế. Bỏ qua hằng số 0.5 và thành phần bậc thấp 0.5n. Độ phức tạp thời gian: O(n²).

4. Vòng lặp với bước nhảy không phải là hằng số (ví dụ: chia đôi)

void processLogarithmic(int n) {
    int count = 0;
    for (int i = n; i > 1; i /= 2) {
        // Thao tác O(1)
        count++;
    }
    std::cout << "Number of iterations: " << count << std::endl;
}

Giải thích: Biến i bắt đầu từ n và bị chia đôi sau mỗi lần lặp (i /= 2). Chúng ta cần tìm số lần lặp cho đến khi i nhỏ hơn hoặc bằng 1. Các giá trị của i sẽ là: n, n/2, n/4, n/8, ..., 1. Giả sử vòng lặp chạy k lần. Sau k lần lặp, giá trị của i sẽ khoảng n / 2^k. Chúng ta dừng khi n / 2^k <= 1, tương đương n <= 2^k. Lấy logarit cơ số 2 cả hai vế: log₂(n) <= k. Vậy, số lần lặp khoảng log₂(n). Độ phức tạp thời gian: O(log n).

Ví dụ khác: Tìm kiếm nhị phân (Binary Search) Binary Search hoạt động trên một mảng đã sắp xếp. Ở mỗi bước, nó loại bỏ một nửa mảng tìm kiếm còn lại. Quá trình này lặp đi lặp lại cho đến khi tìm thấy phần tử hoặc không còn phần tử nào để tìm. Tương tự như ví dụ trên, số bước lặp để giảm kích thước mảng từ n xuống 1 là khoảng log₂(n). Độ phức tạp thời gian của Binary Search là O(log n).

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // Found
        } else if (arr[mid] < target) {
            left = mid + 1; // Search in right half
        } else {
            right = mid - 1; // Search in left half
        }
    }
    return -1; // Not found
}

Giải thích: Mỗi lần lặp của vòng while, kích thước phạm vi tìm kiếm (right - left + 1) được giảm đi khoảng một nửa. Vòng lặp dừng khi phạm vi tìm kiếm chỉ còn 1 phần tử hoặc rỗng. Số lần lặp để giảm kích thước từ n xuống 1 là O(log n). Bên trong vòng lặp là các thao tác O(1). Độ phức tạp thời gian: O(log n).

5. Nhiều vòng lặp liên tiếp

void processTwoLoops(int arr[], int n) {
    // Vòng lặp 1
    for (int i = 0; i < n; ++i) {
        // Thao tác O(1)
    }

    // Vòng lặp 2
    for (int i = 0; i < n; ++i) {
        // Thao tác O(1)
    }
}

Giải thích: Vòng lặp đầu tiên có độ phức tạp O(n). Vòng lặp thứ hai cũng có độ phức tạp O(n). Tổng độ phức tạp là O(n) + O(n) = O(2n). Khi sử dụng ký hiệu Big O, chúng ta bỏ qua hằng số. Độ phức tạp thời gian: O(n).

Quy tắc: Khi có các khối lệnh hoặc vòng lặp chạy liên tiếp, chúng ta lấy độ phức tạp của thành phần chậm nhất. Ví dụ: Một thuật toán có một vòng lặp O(n) theo sau là một vòng lặp O(n²). Tổng độ phức tạp là O(n) + O(n²) = O(n²), vì O(n²) tăng trưởng nhanh hơn O(n).

6. Câu lệnh điều kiện (if/else)

void processConditional(int arr[], int n) {
    if (n > 1000) {
        // Khối lệnh A - giả sử O(n^3)
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    // O(1)
                }
            }
        }
    } else {
        // Khối lệnh B - giả sử O(n)
        for (int i = 0; i < n; ++i) {
            // O(1)
        }
    }
}

Giải thích: Với câu lệnh điều kiện, chúng ta thường xem xét trường hợp xấu nhất (worst case). Trường hợp xấu nhất là đường đi (path) trong code mà tiêu tốn nhiều tài nguyên nhất. Trong ví dụ này, khối lệnh A có độ phức tạp O(n³), khối lệnh B có độ phức tạp O(n). Trường hợp xấu nhất là khi điều kiện n > 1000 đúng, thuật toán chạy khối A. Độ phức tạp thời gian trong trường hợp xấu nhất: O(n³).

7. Lời gọi hàm

Nếu một hàm funcA gọi một hàm funcB, độ phức tạp của funcA ít nhất bằng độ phức tạp của funcB.

void funcB(int n) {
    // Giả sử funcB có độ phức tạp O(n^2)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // O(1)
        }
    }
}

void funcA(int n) {
    // Vòng lặp O(n)
    for (int i = 0; i < n; ++i) {
        // Thao tác O(1)
    }
    // Lời gọi hàm funcB
    funcB(n);
}

Giải thích: funcA thực hiện một vòng lặp O(n) và sau đó gọi funcB có độ phức tạp O(n²). Tổng độ phức tạp là O(n) + O(n²) = O(n²). Độ phức tạp thời gian của funcA: O(n²).

8. Trường hợp tốt nhất, xấu nhất và trung bình (Best, Worst, and Average Case)

Trường hợp xấu nhất (Worst Case): Lượng tài nguyên (thời gian/bộ nhớ) tối đa mà thuật toán có thể tiêu tốn với bất kỳ đầu vào nào có kích thước n. Đây là trường hợp chúng ta thường quan tâm nhất vì nó đưa ra một đảm bảo về hiệu suất. Ký hiệu Big O (O) thường được dùng để mô tả trường hợp xấu nhất.
Trường hợp tốt nhất (Best Case): Lượng tài nguyên tối thiểu mà thuật toán có thể tiêu tốn. Thường ít hữu ích trong thực tế. Ký hiệu Big Omega (Ω) đôi khi được dùng để mô tả trường hợp tốt nhất.
Trường hợp trung bình (Average Case): Lượng tài nguyên tiêu tốn trung bình trên tất cả các đầu vào có kích thước n (hoặc trên một phân phối xác suất của đầu vào). Phân tích trường hợp trung bình khó hơn nhiều so với trường hợp xấu nhất. Ký hiệu Big Theta (Θ) đôi khi được dùng khi trường hợp tốt nhất và xấu nhất có cùng tốc độ tăng trưởng.

Ví dụ: Tìm kiếm tuyến tính (Linear Search) Tìm một phần tử trong một mảng chưa sắp xếp.

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == target) {
            return i; // Found
        }
    }
    return -1; // Not found
}

Trường hợp tốt nhất: Phần tử cần tìm nằm ở vị trí đầu tiên (i=0). Thuật toán chỉ cần 1 lần so sánh. Độ phức tạp: Ω(1) hoặc O(1) (vì cả cận trên và cận dưới đều là hằng số trong trường hợp này).
Trường hợp xấu nhất: Phần tử cần tìm nằm ở vị trí cuối cùng (i=n-1) hoặc không có trong mảng. Thuật toán phải duyệt qua tất cả n phần tử. Độ phức tạp: O(n).
Trường hợp trung bình: Giả sử phần tử có khả năng xuất hiện ở mọi vị trí là như nhau, và có 50% khả năng nó có mặt trong mảng. Trung bình, chúng ta sẽ phải duyệt khoảng n/2 phần tử. Độ phức tạp: Θ(n) (vì n/2 vẫn tăng trưởng theo bậc n).

Trong đa số trường hợp, khi nói về độ phức tạp của thuật toán mà không nói rõ là trường hợp nào, người ta thường ngầm hiểu là độ phức tạp thời gian trong trường hợp xấu nhất được mô tả bằng ký hiệu Big O.

Độ phức tạp không gian (Space Complexity)

Bên cạnh thời gian, bộ nhớ cũng là một tài nguyên quan trọng cần phân tích. Độ phức tạp không gian của một thuật toán đo lường lượng bộ nhớ phụ trợ (auxiliary space) mà thuật toán sử dụng trong quá trình thực thi, không tính bộ nhớ dùng để lưu trữ dữ liệu đầu vào (trừ khi bộ nhớ phụ thuộc vào cấu trúc dữ liệu đầu vào được tạo ra bởi thuật toán).

Phân tích độ phức tạp không gian cũng sử dụng các ký hiệu tiệm cận (Big O, Omega, Theta) tương tự như độ phức tạp thời gian.

Ví dụ về độ phức tạp không gian:

O(1) - Không gian hằng số:

int sumArray(int arr[], int n) {
    int sum = 0; // Sử dụng một số biến cố định, không phụ thuộc n
    for (int i = 0; i < n; ++i) {
        sum += arr[i];
    }
    return sum;
}

Thuật toán này chỉ sử dụng một vài biến cục bộ (sum, i), lượng bộ nhớ này là cố định bất kể n lớn thế nào. Độ phức tạp không gian: O(1).

O(n) - Không gian tuyến tính:

std::vector<int> copyArray(const std::vector<int>& arr) {
    // Tạo một vector mới có kích thước bằng kích thước vector đầu vào
    std::vector<int> newArr(arr.size());
    for (size_t i = 0; i < arr.size(); ++i) {
        newArr[i] = arr[i];
    }
    return newArr;
}

Thuật toán này tạo ra một vector newArr có kích thước tỷ lệ thuận với kích thước vector đầu vào arr. Lượng bộ nhớ phụ trợ cần thiết là O(n) (với n là kích thước của arr). Độ phức tạp không gian: O(n).

Độ phức tạp không gian trong đệ quy: Lời gọi đệ quy sử dụng stack để lưu trữ trạng thái của mỗi lần gọi. Chiều sâu của stack đệ quy có thể ảnh hưởng đến độ phức tạp không gian.
```
int recursiveSum(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + recursiveSum(n - 1);
}
```
Mỗi lần gọi recursiveSum (trừ trường hợp cơ bản) sẽ gọi một phiên bản khác của chính nó và đẩy một khung stack (stack frame) lên stack bộ nhớ. Khi n > 0, hàm sẽ gọi đệ quy cho đến khi n bằng 0. Độ sâu tối đa của stack đệ quy là n. Do đó, độ phức tạp không gian (do stack) là O(n). (Lưu ý: một số trình biên dịch có thể tối ưu hóa đệ quy đuôi để không sử dụng stack O(n), nhưng theo lý thuyết cơ bản thì là O(n)).

Mối quan hệ giữa thời gian và không gian

Thông thường, có một sự đánh đổi giữa độ phức tạp thời gian và độ phức tạp không gian. Đôi khi, bạn có thể làm cho thuật toán chạy nhanh hơn (giảm độ phức tạp thời gian) bằng cách sử dụng thêm bộ nhớ (tăng độ phức tạp không gian), và ngược lại. Quyết định lựa chọn thường phụ thuộc vào ràng buộc của bài toán cụ thể (ví dụ: bộ nhớ có hạn, hay thời gian là yếu tố sống còn).

Bài tập ví dụ:

Sắp xếp chẵn lẻ nhị phân

Trong một buổi chăm sóc vườn rau, FullHouse Dev nhận thấy cách sắp xếp các luống rau theo một quy tắc đặc biệt sẽ giúp việc tưới nước hiệu quả hơn. Điều này khiến họ nghĩ đến một bài toán thú vị về việc sắp xếp các số theo quy luật bit chẵn lẻ.

Bài toán

Cho một mảng \(A\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là sắp xếp lại mảng theo các điều kiện sau và trả về mảng đã sắp xếp:

Các số có số lượng bit 1 chẵn xuất hiện trước theo thứ tự tăng dần.
Tiếp theo là các số có số lượng bit 1 lẻ được sắp xếp theo thứ tự tăng dần.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
Với mỗi test case:
- Dòng đầu tiên chứa số nguyên \(n\).
- Dòng thứ hai chứa mảng \(A\) gồm \(n\) số nguyên.

OUTPUT FORMAT:

Với mỗi test case, in ra mảng đã được sắp xếp theo quy tắc trên trên một dòng mới.

Ràng buộc:

\(1 \leq T \leq 100\)
\(1 \leq n \leq 10^5\)
\(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

1
6
5 2 8 12 7 6

OUTPUT

5 6 12 2 7 8

Giải thích

Với mảng đầu vào [5, 2, 8, 12, 7, 6], kết quả là [5, 6, 12, 2, 7, 8], trong đó:

Các số có số lượng bit 1 chẵn: 5(101), 6(110), 12(1100)
Các số có số lượng bit 1 lẻ: 2(10), 7(111), 8(100) Đây là hướng dẫn giải bài toán Sắp xếp chẵn lẻ nhị phân bằng C++:

Phân tích bài toán:
- Cần sắp xếp mảng theo hai tiêu chí:
  - Số lượng bit 1 là chẵn ưu tiên hơn lẻ.
  - Trong mỗi nhóm (chẵn hoặc lẻ bit 1), các số được sắp xếp tăng dần.
- Kích thước mảng và giá trị các phần tử yêu cầu một giải thuật sắp xếp hiệu quả (thường là O(N log N) hoặc O(N)).
Xác định số lượng bit 1 (population count):
- Đối với mỗi số nguyên x trong mảng, bạn cần tính số lượng bit 1 trong biểu diễn nhị phân của nó.
- Trong C++, có nhiều cách để làm điều này:
  - Dùng vòng lặp và các phép toán bit (&, >>).
  - Sử dụng hàm tích hợp (intrinsic function) của trình biên dịch như __builtin_popcount() (GCC/Clang). Đây là cách hiệu quả nhất.
  - Sử dụng std::popcount() trong C++20.
Xác định tính chẵn/lẻ của số lượng bit 1:
- Sau khi có số lượng bit 1 là count, kiểm tra count % 2. Nếu kết quả là 0, đó là số chẵn; nếu là 1, đó là số lẻ.
Chiến lược sắp xếp:
- Cách tiếp cận hiệu quả và phổ biến là sử dụng hàm sắp xếp có sẵn (std::sort trong C++) kết hợp với một hàm so sánh tùy chỉnh (custom comparator).
- Hàm so sánh này sẽ nhận hai số a và b và trả về true nếu a nên đứng trước b theo quy tắc sắp xếp của bài toán.
Xây dựng hàm so sánh tùy chỉnh (compare(a, b)):
- Tính số lượng bit 1 cho a (count_a) và cho b (count_b).
- Xác định tính chẵn lẻ: parity_a = count_a % 2, parity_b = count_b % 2.
- Logic so sánh:
  - Ưu tiên chẵn trước lẻ: Nếu parity_a khác parity_b, số có parity 0 (chẵn) sẽ đứng trước số có parity 1 (lẻ). Tức là, nếu parity_a < parity_b (0 < 1), thì a đứng trước b. Trả về parity_a < parity_b.
  - Nếu cùng chẵn hoặc cùng lẻ: Nếu parity_a bằng parity_b, thì sắp xếp theo giá trị tăng dần của bản thân số đó. Tức là, nếu a < b, thì a đứng trước b. Trả về a < b.
Thực hiện trong mã C++:
- Đọc số lượng test case T.
- Trong mỗi test case:
  - Đọc số lượng phần tử n.
  - Đọc n phần tử vào một std::vector<int>.
  - Gọi std::sort trên vector này, truyền thêm hàm so sánh tùy chỉnh bạn đã xây dựng.
  - In các phần tử của vector đã được sắp xếp ra màn hình.
Lưu ý:
- Bao gồm các header cần thiết: <iostream>, <vector>, <algorithm>, và có thể cần <bit> (cho std::popcount C++20) hoặc biết cách dùng intrinsic (__builtin_popcount).
- Sử dụng long long cho các biến đếm lớn nếu cần, nhưng ở đây A[i] <= 10^9 nên int và __builtin_popcount là đủ.
- Đảm bảo xử lý nhiều test case đúng cách.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.