giúp mình tính độ phức tạp giải thuật này với

[hvdnghia3]

nhờ các bạn làm giúp mình bài này :

tính độ phức tạp giải thuật của đoạn chương trình sau [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]những đoạn được đánh số)
a. [1] sum := 0;
[2] for i:= 1 to n do begin
[3] readln(x);
[4] sum := sum + x;

end;
b.
function search (a:array [1..n] of integer; x : integer) : boolean;
var i:integer; found : boolean;
begin
[1] i:=1;
[2] found := false;
[3] while (i<n) and (not found) do
[4] if A = x then found := true else i := i + 1;
[5] search := found;
end;
c. giải thích tại sao "một thuật toán có cấp O(1) cũng có thể viết là O(logn)" {đối với câu a}
và "O(n) cũng có thể viết là O(n.logn)" {đối với câu b}

[hoabaybay]

a, O(N)
b, O(N)
c, mình chưa bao giờ nghe nói đến việc O(1) có thể viết là O(logN). Ý nghĩa khác hẳn nhau. Bạn lấy đề bài ở đâu ra thế??? Cả chuyện O(N) có thể viết là O(NlogN) cũng vậy.

[canhotanbinh]

Các bạn nói kĩ hơn phần độ phức tạp của thuật toán cho mình nghe với. Mình không thạo phần này cho lắm.
Ở câu a) Có phải là readln(x) có độ phức tạp là O(1)
sum:=sum+x cũng có độ phức tạp là O(1)
Vậy câu lệnh ghép đó có độ phức tạp là max(O(1),O(1))=O(1)
và câu lệnh đó được thực hiện n lần nên độ phức tạp là n*O(1)=O(n)
Các bác cho em hỏi em hiểu khi thế có đúng không nhỉ?

[shinchao]

mà bài của thoden.it có chỗ này chưa chuẩn
Đó là khai báo mảng trong chương trình con thì không viết a:array[1..n] of integer được mà phải khai báo kiểu trước đã, không khai báo như vậy được
b.
function search (a:array [1..n] of integer; x : integer) : boolean;
var i:integer; found : boolean;
begin
[1] i:=1;
[2] found := false;
[3] while (i<n) and (not found) do
[4] if A = x then found := true else i := i + 1;
[5] search := found;
end;

[sonseoer001]

em học Visual Basic em k học cái này!pác nào có thắc mắc gì về Vb thì em có thể jjup!
còn cái này thì chịu!

[tuongts]

@ lehang_gb1: Mình cũng không phải là chuyên gia tin học, nên chỉ có thể nói một số điều mình biết thôi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Nói một cách đơn giản thì độ phức tạp của một thuật toán có thể xác định qua các vòng lặp và các ct đệ quy.

VD đoạn code sau

for t := 1 to n do
    for k := m downto 1 do
        a[t, k] := t-k;

Độ phức tạp sẽ là O(N.M)

Trong vòng lặp có thể có nhiều phép toán được thực hiện, nhưng độ phức tạp thường chỉ tính dựa vào vòng lặp thôi. VD đoạn code sau:

t1 := 1;
t2 :=2;
t3 :=3;
for t := 1 to n do
begin
    t1 := t1 + n - t2;
    t2 := t2 - n + t3;
    t3 := t3 + n div 2;
    t4 := t1 + t2 + t3;
end;

Trong vòng lặp có 4 phép toán được thực hiện nhưng độ phức tạp vẫn chỉ là O(N) {Ở đây cũng hiểu là O(4.N) nhưng thường thì những hằng số nhỏ như vậy thì sẽ được bỏ qua}

Các đoạn chương trình đệ qui thì cũng có thể tính được độ phức tạp: như chương trình sinh (kiểu sinh hoán vị) thì sẽ là O(N!), chương trình tìm kiếm nhị phân thì sẽ là O(logN), chương trình của thuật toán sắp xếp nhanh (quick sort) thường được cho là O(N.logN).

Trong một chương trình lớn sẽ bao gồm một hoặc nhiều đoạn chương trình con, và độ phức tạp của chương trình lớn chính là độ phức tạp của chương trình con có độ phức tạp lớn nhất.

Việc đánh giá độ phức tạp của một chương trình giúp ước lượng thời gian chạy của chương trình. Điều này là đặc biệt quan trọng cho các bạn học sinh muốn tham gia các kì thi tin học, vì nếu nắm vững khái niệm này các bạn (đôi lúc) có thể nhìn vào giới hạn của bài toán rồi nhẩm được độ phức tạp "khả thi", từ đó "khoanh vùng" được các thuật toán -> hạn chế được việc suy nghĩ lan man không có phương hướng rõ ràng.

Tuy nhiên thì cũng có một số trường hợp chương trình có độ phức tạp lớn hơn lại chạy nhanh hơn chương trình có độ phức tạp nhỏ hơn. Vì thế độ phức tạp cũng chỉ là một thước đo tương đối, nên việc học tập, thực hành và sử dụng cái thước đo này như thế nào là tuỳ vào bạn. Kể cả việc nó có giúp ích được gì cho bạn không thì cũng tuỳ vào bạn sử dụng nó như thế nào.

[freedomf]

a, O(N)
b, O(N)
c, mình chưa bao giờ nghe nói đến việc O(1) có thể viết là O(logN). Ý nghĩa khác hẳn nhau. Bạn lấy đề bài ở đâu ra thế??? Cả chuyện O(N) có thể viết là O(NlogN) cũng vậy.

đây là đề thi kết thúc học phần của môn cấu trúc rời rạc trường mình đấy, đề năm ngoái của khóa 2007


bạn đọc trong tài liệu cấu trúc rời rạc đi :
mình nếu đầy đủ lun cho coi nhé

theo định nghĩa về độ phức tạp tính toán:
- một thuật toán cấp O(1) cũng có thể viết là O(logn)
- một thuật toán cấp O(logn) cũng có thể viết là O(n)
- một thuật toán cấp O(n) cũng có thể viết là O(n.logn)
- một thuật toán cấp O(n.logn) cũng có thể viết là O(n^2)

[traveldatviet]

mà bài của thoden.it có chỗ này chưa chuẩn
Đó là khai báo mảng trong chương trình con thì không viết a:array[1..n] of integer được mà phải khai báo kiểu trước đã, không khai báo như vậy được
b.
function search (a:array [1..n] of integer; x : integer) : boolean;
var i:integer; found : boolean;
begin
[1] i:=1;
[2] found := false;
[3] while (i<n) and (not found) do
[4] if A = x then found := true else i := i + 1;
[5] search := found;
end;

cậu có thể giải thích rõ hơn cho mình được không. :emlaugh:

[tuylasg]

Eo! Học CNTT sướng quá ta. Mấy cái này thì đâu cần suy nghĩ gì nhiều đâu he.

[ductri2102]

Eo! Học CNTT sướng quá ta. Mấy cái này thì đâu cần suy nghĩ gì nhiều đâu he.

Smod mà cũng tham gia spam hả. không tốt không tốt.

nhờ các bạn giải thích giùm mình vì sao lại thế này là được :
tại sao có thể nói :
- một thuật toán cấp O(1) cũng có thể viết là O(logn)
- một thuật toán cấp O(logn) cũng có thể viết là O(n)
- một thuật toán cấp O(n) cũng có thể viết là O(n.logn)
- một thuật toán cấp O(n.logn) cũng có thể viết là O(n^2)