Đáp án + Giải thích các bước giải:

Câu 20:

n = 100000
for i in range (n):
    if i % 5 == 0:
        print (i)

$\bullet$ Tính thời gian thực hiện đoạn chương trình:

$-$ Lệnh gắn giá trị $\tt 100000$ cho biến $\tt n$ cần $\tt 1$ đơn vị thời gian

$-$ Vòng lặp $\texttt {for i in range (n)}$ chạy từ $\tt 0$ đến $\tt 99999$, mỗi bước tăng giá trị của $\tt i$ lên $\tt 1$ đơn vị

$\rightarrow$ Vòng lặp trải qua $\tt 100000$ bước lặp

$-$ Mỗi bước lặp của vòng lặp trên là một lần thực hiện kiểm tra điều kiện $\texttt {if i % 5 == 0}$, mỗi lần thoả mãn điều kiện thì sẽ thực hiện lệnh $\texttt{print (i)}$ tốn $1$ đơn vị thời gian

$\Rightarrow$ Cả vòng lặp $\texttt{for}$ sẽ tốn $\tt 1 \cdot \bigg \lfloor \dfrac{99999}{5} \bigg \rfloor = 19999$ lần, trong đó $\tt \lfloor x \rfloor$ là số nguyên lớn nhất nhỏ hơn $\tt x$

$\Rightarrow$ Đoạn chương trình trên tốn $\tt 1 + 19999 = 20000$ đơn vị thời gian

Câu $21$:

def BubbleSort (A)
    n = len (a)
    for i in range (n - 1)
        for j in range (n - 1 - i):
            if A[j] > A[j + 1]
                A[j], A[j + 1] = A[j + 1], A[j]

a) Những lỗi trong đoạn chương trình:

$-$ Thiếu dấu $\tt :$ trong các dòng $1, 3, 5 ($cuối mỗi lệnh $\tt def, if, for$ đều cần có dấu $\tt :$$)$

$-$ $\tt n$ được định nghĩa là độ dài của mảng $\tt A$ nhưng lại ghi $\tt len(a)$, trong đoạn chương trình không có đối tượng nào tên là $\tt a$

Sửa lỗi: thêm dấu $\tt :$ vào cuối các dòng $1, 3, 5$, sửa dòng $2$ thành $\tt n = len (A)$

b) Tính thời gian thực hiện đoạn chương trình:

$-$ Gắn giá trị $\texttt{len (A)}$ cho biến $\tt n$ mất $1$ đơn vị thời gian

$-$ Vòng lặp ngoài $\texttt {for i in range (n - 1)}$ chạy từ $\tt 0$ đến $\tt n - 1$, mỗi bước tăng giá trị của $\tt i$ lên $\tt 1$ đơn vị

$-$ Mỗi bước lặp ở vòng lặp ngoài phải thực hiện vòng lặp trong $\texttt {for j in range (n - 1 - i)}$, chạy từ $\tt 0$ đến $\tt n - 1 - i$, mỗi bước tăng giá trị của $\tt j$ lên $\tt 1$ đơn vị

$\rightarrow$ Vì $\tt i$ chạy từ $0$ đến $\tt n - 1$, mỗi lần tăng $\tt 1$ đơn vị nên cả $2$ vòng lặp có tối đa $\tt (n - 1) + (n - 2) + ... + 1 = \dfrac{n(n - 1)}{2}$ bước lặp

$-$ Mỗi bước lặp ở vòng lặp trong phải thực hiện kiểm tra điều kiện $\texttt {if A[j] > A[j + 1]}$, nếu thoả mãn điều kiện thì thực hiện phép hoán đổi $2$ phần tử liền nhau $\tt A[j], A[j + 1] = A[j + 1], A[j]$ cần $1$ đơn vị thời gian

$\rightarrow$ Trong trường hợp xấu nhất là mỗi bước lặp đều thoả mãn điều kiện, cả $\tt 2$ vòng lặp sẽ cần $\tt \dfrac{n(n - 1)}{2} =\dfrac{1}{2}(n^2 - n)$ đơn vị thời gian

$\Rightarrow$ Thuật toán cần nhiều nhất $\tt \dfrac{1}{2}(n^2 - n) + 1$ đơn vị thời gian

$\Rightarrow$ Độ phức tạp của thuật toán là $O\bigg(\dfrac{1}{2}(n^2 - n) + 1\bigg) = O(n^2 - n) = O(\max (n^2, -n)) = O(n^2)$