Anh chị giải thích giúp em về cách tính trung bình các phép so sánh của linear search với ạ.
Đề bài:
Analyze the average-case performance of the linear search algorithm, if exactly half the time the element x is not in the list, and if x is in the list, it is equally likely to be in any position
Em xem hướng dẫn giải trên mạng thì thấy họ lấy 1/2 x (tổng số phép so sánh khi x không thuộc list + số phép so sánh trung bình khi x thuộc list)
Còn theo em suy nghĩ là lấy 1/2 x (số phép so sánh trung bình khi x không thuộc list + số phép so sánh trung bình khi x thuộc list).
Em không biết lí do người ta giải như vậy, mong mọi người giúp đỡ.
Hướng dẫn trên mạng:
tổng số phép so sánh khi x không thuộc list là n, em nghĩ tính trung bình ra sẽ là n/n = 1, sao lại là n được anh nhỉ
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?