Độ phức tạp và so sánh thuật toán Distribution Counting Sort với các thuật toán sắp xếp khác

minhcanhtu · September 2, 2018, 5:43am

Trong chương III của cuốn TLCT1 có nói về thuật toán sắp xếp đếm bằng phân phối (Distribution Counting) như sau:

Trong trường hợp khóa của các phần tử a[1], a[2], …, a[n] là các số nguyên nằm trong khoảng từ 0 đến K, ta có thuật toán đơn giản và hiệu quả như sau:
Xây dựng dãy c[0], c[1], …, c[K], trong đó c[V] là số lần xuất hiện khóa V trong dãy.
for V := 0 to K do c[V] := 0; {Khởi tạo dãy c}
for i := 1 to n do c[a[i].key] := c[a[i].key] + 1;
Như vậy, sau khi sắp xếp:

Các phần tử có khóa bằng 0 đứng trong đoạn từ vị trí 1 tới vị trí c[0].

Các phần tử có khóa bằng 1 đứng trong đoạn từ vị trí c[0] + 1 tới vị trí c[0] + c[1].

Các phần tử có khóa bằng 2 đứng trong đoạn từ vị trí c[0] + c[1] + 1 tới vị trí c[0] + c[1] + c[2].
…

Các phần tử có khóa bằng V đứng trong đoạn từ vị trí c[0] + c[1] + … + c[V-1] + 1 tới vị trí c[0] + c[1] + … + c[V - 1] + c[V].
…

Các phần tử có khóa bằng K đứng trong đoạn từ vị trí c[0] + c[1] + … + c[K - 1] + 1 tới vị trí c[0] + c[1] + … + c[K].

VD: …
Độ phức tạp của thuật toán là: O(max(N, K)).

Mình tiến hành cài đặt thuật toán như sau:
Code: https://ideone.com/FriBIt

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void DisCountSort(vector<int> &arr, int n)
{
    auto _max = max_element(arr.begin(), arr.end());
    int max_val = *_max;
    arr.clear(); // begin to sort arr
    vector<int> c(max_val + 1, 0); // number of times that index value appears
    for (int i = 0; i < n; ++i) c[arr[i]] += 1;
    auto it = arr.begin();
    for (int i = 0; i < max_val + 1; ++i) {
        if (c[i] > 0) {
            arr.insert(it, c[i], i);
            it = arr.end();
        }
    }
}

int main()
{
    vector<int> arr{30, 90, 60, 70, 10, 60, 30, 70, 100, 50, 70};
    DisCountSort(arr, arr.size());
    for (auto &it : arr) cout << it << " ";
    return 0;
}

Cho mình hỏi là cách cài đặt của mình có đảm bảo độ phức tạp O(max(N, K)) của thuật toán trên lý thuyết ko ạ? Nếu không thì cho mình hỏi những cho cần cải tiến?
Xin cảm ơn!

P/S: Trong trường hợp này std::insert của vector là O(1) đúng không ạ? (vì nó được đặt trong vòng for O(K) mà nếu ko phải O(1) thì đpt khác với đpt yêu cầu ban đầu của thuật toán?)

rogp10 · September 2, 2018, 6:16am

Sai rồi, theta(N + k) mới đúng chứ max(N, k) thì là lúc O(N) lúc O(k) cơ.

insert nhét 1 lần count phần tử nên một mình nó là O(count), it = arr.end vậy mỗi pt là O(1).

minhcanhtu · September 2, 2018, 9:55am

Mình chỉ biết ký pháp bigO chứ ko biết Theta bạn ? Vậy thì độ phức tạp của thuật toán trên là O(N*K) hả bạn?

Mình chưa hiểu chỗ này lắm ?

Có 1 anh chỉ cho mình cách kiểm tra “chất lượng” code bằng cách cho code chạy trong trường hợp xấu nhất như sau: https://ideone.com/cDikmr
Mình chưa hiểu vì sao vòng for trong main() lại chạy từ 0 đến 1000111 và push_back vào vector giá trị 1 vậy bạn?

rogp10 · September 2, 2018, 10:56am

Theta thì == luôn. N + K là vì N và K là hai biến độc lập (K đâu có bằng cN với c là hằng số, nên bỏ không được).

Thực ra code viết sai một chỗ là vì sao lại xóa clear arr trước gồm 3 phần:

khởi tạo (và free) mảng value K slot.
điền bảng tần suất. (theta(n))
chèn trở lại theo bảng. (truy cập k ô nhớ và chèn n phần tử: theta(n+k))

Xem docs: https://en.cppreference.com/w/cpp/container/vector/insert chèn trước vector::end() tức là chèn vào cuối nên O(1) cho lần chèn đó, cộng thêm mỗi phần tử là O(1) nữa.

minhcanhtu · September 2, 2018, 1:28pm

Mình chưa hiểu bạn nói chỗ này lắm, bạn có thể nói rõ hơn chỗ này đc ko?

rogp10 · September 2, 2018, 1:55pm

Bảng tần số (whoops ) là bảng ghi các giá trị và số lần xuất hiện của mỗi giá trị.

Trở lại thì không nên bỏ qua việc khởi tạo mảng phụ c khi tính big-O (trừ zeroize - gán bằng 0). Tiếp theo, c[arr[i]] += 1; là O(1), vậy đoạn này là O(N). Đoạn sau đọc c từ 1 đến K là O(K), rồi chèn vào arr số phần tử đọc được. Mỗi lượt chèn vào đuôi là O(1) (xem thuật toán chèn mảng), sau khi dọn xong thì chép vào O(1) mỗi phần tử, vậy đoạn sau là O(N+K). Tóm lại, thuật toán có độ phức tạp O(N+K).

minhcanhtu · September 3, 2018, 1:45am

Vậy mình có cách nào cải thiện thành đúng O(max(N, K)) không bạn?

Vậy mình nên đặt dòng arr.clear() vào chỗ nào là hợp lý bạn? (vì mình chỉ muốn xóa toàn bộ để push_back vào những giá trị đã sắp xếp, nhưng việc push_back từng phần tử dẫn đến phải tạo thêm 1 vòng lặp con lặp đến c[i] để push_back nên mình quyết định dùng insert)

noname00 · September 3, 2018, 4:04am

O(N + K) = O(max(N, K)) theo quy tắc cộng trong big-O mà? Bạn còn đòi hỏi gì nữa?

Thế nên bài này đánh giá độ phức tạp là Θ(N + K) mới chuẩn xác nhất.

rogp10 · September 5, 2018, 10:28am

Thực ra sách thường chỉ định nghĩa big-O một biến (thậm chí không có mà chỉ có đồ thị), trong khi hàm T có thể có hai biến nên có thể xem M + N là có đầy đủ hai tham số, còn max(M, N) chỉ là một tham số (như hàm gcd).