Average-case Complexity,
Example: Linear Search
Code: LinearSearch (var R: RA type; a, b, x: integer): boolean
var i integer; found: boolean;
i := a;
found := false
while (i ≤ b ) and not found
found := R[i] = = x
characteristic operation
i++
LinearSearch := found
Algorithm has infinite instances, but all can be categorized into (n+1) classes:
x = R[1], x = R[2], x = R[3], … x = R[n], x  R
-
i
|
I nstance
|
pi
|
Ti(n)
|
1
|
x = R[1]
|
p/n
|
1
|
2
|
x = R[2]
|
p/n
|
2
|
i
|
x = R[i]
|
p/n
|
i
|
n
|
x = R[n]
|
p/n
|
n
|
n+1
|
x R[1… n]
|
1 – p
|
n
|
Share with your friends: |
