25.1

Lời giải chi tiết:

25.2

Lời giải chi tiết:

ಌHàm trên thực hiện việc tìm phần tử lớn nhất của mảng A.

🍰Gọi n là kích thước của mảng, T(n) là thời gian thực hiện của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

– Câu lệnh tại dòng 2 cần 1 đơn vị thời gian.

🦩– Vòng lặp for tại dòng 3 biến i chạy từ 1 đến n − 1, nên vòng lặp có n – 1 bước lặp.

﷽– Với mỗi bước lặp chương trình thực hiện 1 lệnh so sánh tại dòng 4 và 1 lệnh gán tại dòng 5 (nếu điều kiện thoả mãn).

– Lệnh trả về tại dòng 6 cần 1 đơn vị thời gian.

♔Tổng hợp lại chương trình trên có thời gian chạy là

T(n) = 2 + 2(n-1) = 2n = O(n).

25.3

𒁏Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.

Lời giải chi tiết:

♚Hàm trên thực hiện in ra xâu đảo ngược của xâu đầu vào.

♛Gọi n là kích thước của xâu đầu vào (số kí tự của xâu), T(n) là thời gian thực hiện

♔của chương trình. Thời gian chạy của chương trình được phân tích như sau:

ꩵ– Câu lệnh tại dòng 2 và 3 cần 2 đơn vị thời gian.

– Vòng lặp while thực hiện n lần lặp.

𓄧– Với mỗi bước lặp chương trình thực hiện hai lệnh gán tại dòng 5 và 6.

– Lệnh trả về tại dòng 7 cần 1 đơn vị thời gian.

𓄧Tổng hợp lại chương trình trên có thời gian chạy là T(n) = 2 + 2n+1 = 2n + 3 = O(n).

25.4

ﷺEm hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A.

Lời giải chi tiết:

꧒Gọi n là kích thước của mảng, T(n) là thời gian thực hiện của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

– Câu lệnh tại dòng 2 cần 1 đơn vị thời gian.

ꦚ– Vòng lặp for tại dòng 3 biến i chạy từ 1 đến n − 1, nên vòng lặp có n – 1 bước lặp.

– Với mỗi bước lặp chương trình thực hiện:

• Hai lệnh gán tại dòng 4 và 5.

♛• Vòng lặp while tại dòng 6. Vòng lặp này sẽ chạy tối đa là i lần. Mỗi lần lặp chương trình sẽ thực hiện hai lệnh gán tại dòng 7 và 8, cần 2 đơn vị thời gian. • Lệnh gán tại dòng 9 cần 1 đơn vị thời gian.

🎃Tổng hợp lại chương trình trên có thời gian chạy tối đa là:

25.5

Xác định độ phức tạp thời gian của hàm sau:

Lời giải chi tiết:

🌞Gọi T(n) là thời gian thực hiện của chương trình. Thời gian chạy của chương trình được phân tích như sau:

– Lệnh gán tại dòng 2 cần 1 đơn vị thời gian.

𓂃– Vòng for tại dòng 3, biến i chạy từ 1 đến n, nên vòng lặp có n bước lặp.

– Với mỗi bước lặp trên, chương trình thực hiện

🔯• Vòng lặp tại dòng 4, biến j chạy từ 1 đến i, nên vòng lặp thực hiện i bước lặp. • Với mỗi bước lặp:

🐼a Chương trình thực hiện vòng lặp tại dòng 5, biến k chạy từ j đến j + vòng lặp có i + 1 bước lặp.

𝓰a Với mỗi bước lặp chương trình thực hiện 1 lệnh gán tại dòng 6 cần 1 đơn vị thời gian.

– Lệnh trả về tại dòng 7 cần 1 đơn vị thời gian.

Tổng hợp lại, hàm trên có thời gian chạy là:

25.6

ꦡNếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?

Lời giải chi tiết:

ജKhông. Ví dụ f(n) = n, g(n) = n2 thì rõ ràng f(n) = O(g(n)) nhưng ngược lại không đúng.

25.7

Giả sử f(n) = an* + a,.n*?

Lời giải chi tiết:

🍰Theo Quy tắc 1, ta có O(f(n)) = O(max(a,.nk, ak-1-nk-1, ...,

Vậy suy ra f(n) = O(nk).

',..., n,.a, a) = O(nk).