Xác định độ phức tạp tính toán

Nếu tương ứng với P1 và P2 là T1(n: O(f(n)), T2(n: O(g(n)) thì thời gian thực hiện P1 và P2

lồng nhau sẽ là

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à

.Đặ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 điểm của giảI thuật đệ quy

Để 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:

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

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

Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc

Chọn câu trả lời đúng nhất về thuật toán

.Đặc trưng của thuật toán

Đặ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

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à

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

Danh sách tuyến tính là:

ưu đIểm của việc càI đặt danh sách bằng mảng