Tư tưởng của giải thuật tìm kiếm nhị phân:
A. Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy,Dựa vào bước so sánh này quuyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành
B. Dựa vào Tư tưởng "chia để trị
C. So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khoá cần tìm
Giải bởi Vietjack
Chọn đáp án A
Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì If E Then S1 Else S2
Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là
Để viết chương trình chỉ để sử dụng một số ít lần và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chương trình thì ta chọn thuật toán:
.Đặc đIúm nào của giảI thuật viết bằng đệ quy là sai trong các đặc đIúm sau
Đặc trưng nào của thuật toán thể hiện: Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản
Khi viết các chương trình (thủ tục hoặc hàm ) để sử dụng nhiều lần, cho nhiều người sử dụng ta chọn thuật toán:
sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình Chú ý: (log2n) = Log cơ số 2 của n
Qui tắc tổng Xác định độ phức tạp tính toán
Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai đoạn chương trình P1 và P2 mà T1(n: O(f(n)); T2(n: O(g(n)) thì thời gian thực hiện đoạn P1 rồi P2 tiếp theo sẽ là
Thời gian thực hiện các lệnh đơn : gán, đọc, viết là Chú ý: (log2n) = Log cơ số 2 của n; n^2 = n mũ 2
Khi khai báo type T = min..max
Trong đó min và max là cận dưới và cận trên của khoảng T là kiểu gì?
Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện tưng bước lần lượt là O(n2), O(n3) và O(nlog2n). thời gian thực hiện chương trình sẽ là
Chú ý: (log2n) = Log cơ số 2 của n; n^2 = n mũ 2
