10/18/2021
4
Thuật toán vét cạn
•Bài toán 2. Thuật toán sắp xếp lựa chọn
•Lần lượt chọn phần tử lớn nhất trong dãy hiện tại, đổi
chỗ với phần tử ở cuối dãy
•Lặp lại bước trên nhưng chỉ xét dãy mới là n-1 phần
tử đầu
•Nhận xét
•Thuật toán xây dựng lời giải từng bước từ lời giải bộ
phận
•Bước kiểm tra đã nằm sẵn trong bước xây dựng
phương án lựa chọn
selectionSort(A[0..n-1])
{
for i=n to 2 do
min = 0
for j=0 to i-1 do
if (A[j]>A[min]) min = j
SWAP(A[min], A[i-1])
}
𝑇(𝑛) = 𝑂(𝑛2)
VD. 1, 5, 12, 3, 2, 4 1, 5, 4, 3, 2,12 1, 2, 4, 3, 5, 12 1, 2, 3, 4, 5, 12 1, 2, 3, 4, 5, 12 1, 2, 3, 4, 5, 12
10/15/2021 hiep.nguyenduy@hust.edu.vn 7
Thuật toán vét cạn
•Bài toán 3. Tính giá trị đa thức bậc n: 𝑃
𝑥 = 𝑎𝑥+ 𝑎𝑥+. . +𝑎𝑥 + 𝑎
Algorithm1(A[0..n], x)
P = 0
For i=n to 0 do
power = 1;
for j=1 to i do
power = power * x
P = P+a[i]*power
Return P
Algorithm2(A[0..n], x)
P = a[0]
For i=n to 1 do
power = a[n];
P = (P+a[i])*x
Return P
𝑇2(𝑛) = 𝑂(𝑛)
𝑇1(𝑛) = 𝑂(𝑛2)
10/15/2021 hiep.nguyenduy@hust.edu.vn 8
