Độ 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
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?)
Sai rồi, theta(N + k) mới đúng chứ max(N, k) thì là lúc O(N) lúc O(k) cơ.
insertnhét 1 lầncountphần tử nên một mình nó là O(count), it = arr.end vậy mỗi pt là O(1).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?
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
cleararr trước gồm 3 phần:Kslot.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.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?
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ụ
ckhi 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 đọcctừ 1 đến K là O(K), rồi chèn vàoarrsố 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).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 đếnc[i]để push_back nên mình quyết định dùng insert)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.
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).