Độ phức tạp thuật toán

Độ phức tạp thuật toán

Hiện tại mình rất cần tính độ phức tạp thuật toán quay lui của bài toán Liệt kê dãy nhị phân có độ dài N, bài toán xếp Hậu.

Bạn thử viết sơ qua cái thuật toán của bạn cái, chứ chẳng nhẽ bây giờ ai đó muốn trả lời bạn lại phải giở sách để tìm thuật toán của bạn à. Hơn nữa cùng một bài toán có thể có nhiều thuật toán với độ phức tạp khác nhau.

Chương trình liệt kê bằng thuật toán quay lui có thể viết sơ bộ như sau:
procedure Try(i: integer);
var j: integer;
begin
for j:=0 to 1 do
begin
x := j;
if i = n then <thông báo cấu hình tìm được>
else Try(i+1);
end;
end;

Chương trình liệt kê bằng thuật toán quay lui có thể viết sơ bộ như sau:
procedure Try(i: integer);
var j: integer;
begin
for j:=0 to 1 do
begin
x := j;
if i = n then <thông báo cấu hình tìm được>
else Try(i+1);
end;
end;
Đây là bài toán liệt kê dãy nhị phân có độ dài N.

OK! Phép toán cơ sở là phép gán x = j. Độ phức tạp của thuật toán sẽ là số lần thuật toán thực hiện phép gán này. Kí hiệu
T(N) là độ phức tạp của thuật toán.
T(N) = 2*T(N-1) + 2
= 2*(T(N-1) + 1)
T(1) = 2
Thay vào sẽ có T(N) = 2^(N+1) - 2 = O(2^N), tức là độ phức tạp tỉ lệ với số các giá trị mà một chuỗi nhị phân độ dài N có thể biểu diễn.
P/S: Bác đang đọc sách của đại ca Nguyễn Đức Nghĩa hả? Em cũng từng đọc qua quyển sách đó rồi và theo ý kiến của em thì nó rất không hay. Sau này bác học thêm về thuật toán đồ thị mà vẫn phải cày kéo với một rổ code thì bác sẽ biết. Tại sao lại phải dùng Pascal nhỉ, trong khi giải thích ở dạng pseudo-code thì dễ hiểu hơn rất nhiều. Mà em cũng thấy cái thuật toán để liệt kê các xâu nhị phân cũng chán. Làm gì mà phải làm phức tạp và khó hiểu thế. Bác cứ bắt đầu từ 1 xâu toàn 0 và mỗi lần tăng thêm 1 thì sẽ liệt kê ra một xâu. Cách làm này không làm tăng độ phức tạp lên thành O(n * 2^n). Không nhất thiết khi tăng lên 1 thì phải duyệt qua hết n bits trong xâu. Thực tế độ phức tạp của nó vẫn là O(2 ^ n) trong khi lại không phải dùng stack. Mà bác cũng thử tính xem độ phức tạp trung bình để tăng lên 1 là bao nhiêu .

Oh oh,
Cái giải thuật đơn giản của người ta bác đi làm nó phức tạp lên thì có
Câu hỏi cuối cùng của bạn là đúng rồi đấy: thay vì giải thuật sinh trẻ con, bác đi làm một bài toán cộng số lớn. Thêm chút nữa, bác cho nó dừng sinh lúc nào ? lúc i = 2^N hay lúc tất cả các bit đều bằng 1 ? Cả hai phép so sánh cũng tốn kém đấy chứ !

Mấy hôm nay thầy giáo bắt bọn mình tìm một cách tường tận độ phức tạp của từng thuật toán cụ thể. Mình thấy có sự khác nhau giữa các tài liệu thì phải. Ông thầy mình thì cho rằng phép toán sơ cấp được sử dụng ở trong thuật toán đệ quy này là phép toán so sánh, và số các phép so sánh sẽ dùng làm thước đo độ phức tạp tính toán. Có thể dễ dàng chứng minh được số phép so sánh đã thực hiện trong thuật toán này là 2^N vì vậy mà độ phức tạp của nó là O(2^N).