Hiệu quả thuật toán: thời gian chạy và độ phức tạp bộ nhớ

Các Khái Niệm trong Khoa Học Máy Tính

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Giới thiệu về ký hiệu Big-O

Đo mức tăng thời gian và bộ nhớ khi đầu vào tăng
Ví dụ: $O(n)$, $O(n^2)$, $O(log\, n)$
'O' là bậc tăng trưởng, ví dụ O(n) = tuyến tính

Độ phức tạp thời gian - ví dụ văn phòng

Biểu đồ các mức độ phức tạp Big O

$O(1)$ - thời gian hằng - "Liếc nhanh" - "hằng số"
$O(log\,n)$ - tăng chậm theo thời gian - "Chia đống" - "logarit"
$O(n)$ - tăng tuyến tính - "Đọc tài liệu" - "tuyến tính"
$O(n\,log\,n)$ - tăng nhanh hơn - "Xếp chồng" - "tuyến tính-log"
$O(n^2)$ - tăng bậc hai - "So tài liệu" - "bậc hai"

Độ phức tạp bộ nhớ - ví dụ văn phòng

Biểu đồ các mức độ phức tạp Big O

$O(1)$ - bộ nhớ hằng - "Chỗ bàn" - "hằng số"
$O(log\,n)$ - tăng bộ nhớ chậm - "ít ghi chú" - "logarit"
$O(n)$ - tăng tuyến tính - "giấy nhớ" - "tuyến tính"
$O(n\,log\,n)$ - tăng nhanh hơn - "chồng tạm" - "tuyến tính-log"
$O(n^2)$ - tăng bậc hai - "lưới so sánh" - "bậc hai"

Hãy luyện tập!

Các Khái Niệm trong Khoa Học Máy Tính

Preparing Video For Download...