Cho số nguyên dương . Đếm số lượng số nguyên dương sao cho tổng các ước của (trừ ) phải lớn hơn .
Ta duyệt qua từng số nguyên từ rồi tính tổng các ước của mỗi số.
Độ phức tạp thời gian: .
Gọi là tổng các ước của trừ chính nó.
Với mỗi số từ đến , ta duyệt qua tất cả các bội của (không tính , tức là từ trở đi), và tăng lên đơn vị.
Đáp án của bài toán là số lượng từ sao cho .
Thuật toán trên được gọi là "sàng ước". Nhiều người nhầm tưởng thuật toán này có độ phức tạp thời gian lớn, tuy nhiên, vì số lượng bội số không ngừng giảm khi số tăng lên, nên thực chất thuật toán này chạy rất nhanh.
Nếu coi là giới hạn để duyệt , ta có thể tính được độ phức tạp thời gian của thuật toán này như sau:
Độ phức tạp thời gian: .
Cho số nguyên dương . Đếm số cách tạo ra số có chữ số thỏa mãn các điều kiện sau:
Quay lui đơn thuần, thử tất cả cả trường hợp, sau đó mới kiểm tra có thỏa điều kiện hay không.
Độ phức tạp thời gian: .
Cần đặt thêm nhánh cận vào thuật toán quay lui brute - force (chỉ thử các trường hợp có thể thỏa điều kiện).
Nhánh cận trong thuật toán quay lui được hiểu là những điều kiện để dừng hàm quay lui sớm hơn bình thường hoặc chỉ duyệt qua những trường hợp đúng, nhằm tránh việc duyệt qua những trường hợp thừa (chắc chắn sai). Từ đó giảm thời gian chạy chương trình đáng kể.
Nhánh cận được đặt trong bài trên là các điều kiện của đề bài.
Độ phức tạp thời gian:
Nhận xét:
Ta có thể tính được số cách chọn số còn lại bằng quy hoạch động.
Gọi là số cách tạo dãy độ dài từ các chữ số sao cho không có 2 số liền kề giống nhau.
Công thức quy hoạch động:
Tức là có trường hợp phải duyệt trong thuật toán quay lui nhánh cận ở trên.
Bài toán này cũng có thể được giải bằng thuật toán quy hoạch động nói trên.
Cho một dãy mắt xích có độ bền . Nếu nối mắt xích và thì độ bền của mối nối là với:
Tìm cách sắp xếp các mắt xích sao cho tổng độ bền của các mối nối và độ bền của từng mắt xích là lớn nhất.
Quay lui đơn thuần, thử tất cả cả trường hợp tất cả trường hợp sắp xếp của mảng rồi lấy tổng lớn nhất.
Độ phức tạp thời gian: .
Nhận xét: Tổng độ bền các mắt xích không đổi, do đó chỉ cần tìm cách sắp xếp các mắt xích sao cho tổng độ bền của các mối nối lớn nhất.
Không mất tính tổng quát, giả sử có bốn mắt xích được xếp liền kề nhau thỏa mãn thì ta có tổng độ bền của các mối nối là:
Thay vì thêm mắt xích vào giữa và , ta nên xếp và vào cùng một mối nối ngay từ đầu, để có thể dùng và vào một mối nối khác. Khi đó tổng độ bền ta đạt được là:
Vậy để đạt độ bền lớn nhất thì ta sẽ lặp đi lặp lại thao tác lấy mối nối nhỏ nhất chưa được nối và nối với mối nối lớn nhất chưa được nối.
Do đó, ta sắp xếp mảng tăng dần: và thực hiện nối như sau:
Nếu sắp xếp dựa theo mối nối, ta được mảng:
nối với , nối với , …
Đáp án:
Độ phức tạp thời gian: .