Kiểm tra kiến thức về độ phức tạp tính toán

Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện tưng bước lần lượt là O(n2), O(n3) và O(nlog2n). thời gian thực hiện chương trình sẽ là:

• O(nlog2n)

• O(n^2)

• O(n^2)+ O(n^3) + O(nlog2n)

• O(n^3)

Xác định độ phức tạp tính toán khi thực hiện P1 và P2 lồng nhau với T1(n) = O(f(n)) và T2(n) = O(g(n))

• T1(n)T2(n) = O(f(n)+g(n))

• T1(n)T2(n) = O(f(n)g(n))

• T1(n)T2(n) = O(f(n)and g(n))

• T1(n)T2(n) = O(f(n)/g(n))

Thời gian thực hiện các lệnh đơn : gán, đọc, viết là

• O(1)

• O(2)

• O(log2(n))

• O(n)

Thời gian thực hiện lệnh hợp thành(Begin.. end) được xác định bởi:

• O(log2(n))

• Hằng số

• Quy tắc nhân

• quy tắc tổng

Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì: If E Then S1 Else S2. Khi đó thời gian thực hiện lệnh if là:

• O(And (f()n), g(n)))

• O(max (f()n), g(n)))

• O(Min (f()n), g(n)))

• O(or( (f()n), g(n)))

Nếu S là câu lệnh và E là biểu thức logic thì: while E do S. Khi đó thời gian thực hiện lệnh while là:

• O(f(n)g(n))

• O(max (f()n), g(n)))

• O(And (f()n), g(n)))

• áp dụng quy tắc tổng

Tính thời gian thực hiện của Hàm sau: function Euclid (m, n : integer) :integer;

• O(log2n)

• 2log2n + 1

• O(1)

• O(n)

Lệnh (1) trong hàm Euclid có thời gian thực hiện là:

• O(m)

• O(2)

• O(n)

• O(1)

Lệnh (6) trong hàm Euclid có thời gian thực hiện là:

• O(m)

• O(n)

• O(1)

• O(2)

Ba lệnh (3), (4) và (5) trong hàm Euclid. Mỗi lệnh có thời gian thực hiện là:

• O(n)

• O(1)

• O(n^2)

• O(m)