Until the recent review to the data structure, summarize the didn't understand what's the worst, the best, an average of time complexity
Best:
Every time just to find data in the data first, namely each number just check again, into the O is expressed as O (1)
The bad:
Just at the end of the data of data to find at a time, a number that is the first to check n times, the second to check n - 1 time, to look up n - two, third, and so on, the last one to find a can, accumulate the is (1 + n) n/2, where each number on average to find (1 + n)/2 times, to O to O (n),
Average (that is, the weighted average) :
This hasn't been read before, now a simple sum up, if an array with n position, each position is just the data you want to check the probability is 1/(1 + n) , (there are n n data, plus a check number is not in the data given by),
The ball check number, check each position to make a few times, obviously, the first location to check 1 time to arrive, the second position to check 2 times to arrive, and the third position check arrive 3 times,,,,,,, check n times to reach the NTH position, a total of 1 + 2 + 3 +,,, + n
Each number on average to find 1/(1 + n) * (1 + 2 + 3 +... N) books n (n + 3)/(n + 1), 2 into O, remove the low order term is O (n),