BỘ CÔNG THƯƠNG CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG ĐẠI HỌC SAO ĐỎ Độc lập - Tự do - Hạnh phúc
***** -----o0o-----
ĐỀ CƯƠNG ÔN TẬP
Môn học: Cấu trúc dữ liệu và giải thuật
Hệ: Đại học
Câu 1
Hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp tồi nhất của đoạn chương trình sau:
1. Read(x); S := 1;
2. For i := 1 to n do
Begin
P := 1;
For j := 1 to i do p := p*x/j;
S := S + p;
End;
Giải.
1,xd phép tích cực p := p*x/j;
2, với i=1->phép tích cực thực hiện 1 lần
i=2->phép tích cực thực hiện 2 lần
.
.
i=n->phép tích cực thực hiện n lần
3.tổng=1+2+..+n=n(n+1)/2;
4.t(n)=O(n2)
Câu 2
Hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp tồi nhất của đoạn chương trình sau:
Read(x); S := 1;
For i := 1 to n do
If M >= 1000 then
For j := 1 to n do
Begin
S := S + x;
Writeln(S:6);
