Câu hỏi:

20/04/2023 239

Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Thuật toán là một chuỗi các bước được thiết kế để giải quyết một vấn đề cụ thể. Một trong những yếu tố quan trọng để đánh giá hiệu suất của một thuật toán là độ phức tạp thời gian, tức là thời gian mà thuật toán mất để thực thi dựa trên kích thước đầu vào của vấn đề. Phân loại thuật toán dựa trên độ phức tạp thời gian là một phương pháp được sử dụng phổ biến để đánh giá và so sánh hiệu suất của các thuật toán khác nhau. Dưới đây là một số phân loại chính dựa trên độ phức tạp thời gian của thuật toán:

-O(1) (độ phức tạp thời gian hằng số): Đây là loại thuật toán có thời gian thực thi không thay đổi theo kích thước đầu vào. Thời gian thực thi của thuật toán này là cố định, vì vậy độ phức tạp thời gian là hằng số. Ví dụ: Truy cập vào phần tử trong mảng có kích thước cố định.

-O(log n) (độ phức tạp thời gian logarithmic): Đây là loại thuật toán có thời gian thực thi tăng theo logarit của kích thước đầu vào. Thuật toán này thường được sử dụng trong các bài toán tìm kiếm nhị phân, các thuật toán chia để trị, hoặc các thuật toán sắp xếp hiệu quả như QuickSort hoặc MergeSort.

-O(n) (độ phức tạp thời gian tuyến tính): Đây là loại thuật toán có thời gian thực thi tăng tỷ lệ trực tiếp với kích thước đầu vào. Ví dụ: Duyệt qua từng phần tử trong mảng một lần.

-O(n^2) (độ phức tạp thời gian bậc hai): Đây là loại thuật toán có thời gian thực thi tăng theo bình phương của kích thước đầu vào. Ví dụ: Thuật toán sắp xếp Bubble Sort, các thuật toán tìm kiếm không hiệu quả như Linear Search trong một mảng lồng nhau.

-O(n^k) (độ phức tạp thời gian bậc k): Đây là loại thuật toán có thời gian thực thi tăng theo lũy thừa của kích thước đầu

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Xác định độ phức tạp thời gian tính toán cho chương trình sau:

n = 1000

sum = 0 

i = 1

while i <n;

               i = i*2

               sum = sum + 1

print (sum)

Xem đáp án » 13/07/2024 2,082

Câu 2:

Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

                                s = s + i*(i+1)

print (s)

Xem đáp án » 13/07/2024 1,993

Câu 3:

Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?

Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian? (ảnh 1)

Xem đáp án » 13/07/2024 1,792

Câu 4:

Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là đúng hay sai?

Xem đáp án » 13/07/2024 1,240

Câu 5:

Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = 2n(n - 2) + 4.

b) T(n) = n3 + 5n - 3.

Xem đáp án » 13/07/2024 1,114

Câu 6:

Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:

a) T(n) = n3 + nlogn + 2n + 1.

b) T(n) = 3n4 + 2n2logn + 10.

Xem đáp án » 13/07/2024 776

Câu 7:

Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài 21.

Xem đáp án » 13/07/2024 552
Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay