30/09/2018, 18:21

[Giúp đỡ]Phân tích thuật toán Kadane

Hiện em đang làm bài tập về phân tích thuật toán Kadane code thì em đã làm được nhưng có điều là về phân tích thuật toán thì em chưa hiểu lắm về nó. Cụ thể là làm sao để tìm được độ phức tạp của một thuật toán ? (em đã search GG rồi cơ mà đọc vẫn chưa hiểu)
Có ví dụ càng tốt ạ .

Itachi Citus viết 20:26 ngày 30/09/2018

Độ phức tạp người ta thường đếm phép so sánh. Lấy đoạn code của python

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Giả sử số phần tử trong A là n.
Phép max là 1 phép so sánh. Trong vòng lặp có 2 phép max, vòng lặp được duyệt n lần, mỗi phần tử duyệt một lần -> Có tổng cộng 2n phép so sánh. 2n < a*n, với a = 3, do đó 2n thuộc nhóm O(n).
-> Thuật toán có độ phức tạp O(n).

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Trịnh Minh Cường

0 chủ đề

0 bài viết

Tác giả nổi bật