Shulou(Shulou.com)06/03 Report--

"introduction to algorithms" about the chain hash hit to find the run time mathematical proof, as soon as the formula is not understood, searched the Internet and did not find the answer to the question of the text, so write this article.

The topic is to calculate the run time of a hit search in a chained hash table in the case of a uniform hash.

Analysis: the running time of the hit search is a function of the number of keys n. According to the cost model, the growth rate of the comparison times of the hit search increases with n, that is, the function T (n) of the comparison times n.

Let's find that the key a _ mena is hashed to the b-linked list. The number of hits and comparisons is + 1 for the number of elements that precede an in the b-linked list. So the title is transformed into key an is inserted into the b-linked list, and all subsequent inserted keys are hashed to the b-linked list by the number of + 1.

Let X denote the number of keys inserted into the b-linked list after key an is inserted into the b-linked list.

Let the random variable Yi denote the indicator random variable in the b-linked list when the key is inserted for the first time. (the indicator random variable is 1 when the event occurs and 0 when it does not occur. This means that when the key is inserted for the first time, the key is hashed into the b linked list as 1, and the hash to other linked lists as 0)

When the random variable Zi represents the first inserted key, select an as the indicator random variable of the inserted key.

Yes

X = ∑ (Zi ∑ Yk) ①

E [Zi] = 1Association ②

E [Yi] = 1 ③

Obtained from the above three formulas

E [X] =. Twenty lines are omitted here. = (nmur1) / (2m)

The expectation of the title is 1 + (nmur1) / (2m) = 1 + α / 2-α / (2n).

T (n) = θ (1 + α)

■

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.