Skip to content

Instantly share code, notes, and snippets.

@joaoventura
Created December 23, 2015 23:24
Show Gist options
  • Save joaoventura/d4aab201dba743b0ce3a to your computer and use it in GitHub Desktop.
Save joaoventura/d4aab201dba743b0ce3a to your computer and use it in GitHub Desktop.
"""
Implements linear search and probabilistic search to analyse time complexity.
"""
import random
from matplotlib import pyplot as plt
def linear_search(value, list):
"""
Searches the index of the value in the list.
Returns the number of iterations.
"""
for index, val in enumerate(list):
if value == val:
return index
return index
def prob_search(value, l):
"""
Searches a value in a list using a probabilistic search.
Returns the number of iterations.
"""
indexes = list(range(len(l)))
random.shuffle(indexes)
for iteration, index in enumerate(indexes):
if l[index] == value:
return iteration
return iteration
def compare_methods(size, n=100):
"""
Returns the average number of iterations for each method to find
a random value in a random list.
"""
values_linear = []
values_prob = []
for _ in range(n):
# Random list
list = random.sample(range(size * 2), size)
# Random value from list
value = random.choice(list)
values_linear.append(linear_search(value, list))
values_prob.append(prob_search(value, list))
return (
sum(values_linear) / len(values_linear),
sum(values_prob) / len(values_prob)
)
def plot_time_complexity(a=10, b=100, step=10, n=100):
"""
Plots time complexity comparison of both search methods for lists with size
between 'a' and 'b'. Each value is an average of 'n' algorithm runs.
"""
values = [(size, compare_methods(size, n)) for size in range(a, b, step)]
steps = [value[0] for value in values]
values_linear = [value[1][0] for value in values]
values_prob = [value[1][1] for value in values]
plt.plot(steps, values_linear, 'b-', label='Linear search')
plt.plot(steps, values_prob, 'r-', label='Probabilistic search')
plt.title('Average number of iterations by list size')
plt.xlabel('List size')
plt.ylabel('Num. iterations')
plt.legend(loc='upper left')
plt.show()
if __name__ == '__main__':
plot_time_complexity(10, 1000, 10)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment