-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathKMP-AnalysisTImeComplexity.py
58 lines (51 loc) · 2.64 KB
/
KMP-AnalysisTImeComplexity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
"""
ASSIGNMENT 2 (Analysis Time Complexity for KMP Algorithm)
MEMBER 1: ANDYCLOS A/L BOON MEE (22300738)
MEMBER 2: MUHAMMAD EZZAT HAZIQ BIN ELHAN (22300604)
MEMBER 3: KAM WENG XUAN (22300683)
MEMBER 4: LOH WEI TING (22300549)
"""
import pandas as pd
import matplotlib.pyplot as plt
# manually input data based on the run experiment
data = [
{"text_size": 1000, "pattern_size": 10, "average_elapsed_time": 19},
{"text_size": 1000, "pattern_size": 20, "average_elapsed_time": 23},
{"text_size": 1000, "pattern_size": 30, "average_elapsed_time": 21},
{"text_size": 1000, "pattern_size": 40, "average_elapsed_time": 23},
{"text_size": 1000, "pattern_size": 50, "average_elapsed_time": 18},
{"text_size": 2000, "pattern_size": 10, "average_elapsed_time": 17},
{"text_size": 2000, "pattern_size": 20, "average_elapsed_time": 15},
{"text_size": 2000, "pattern_size": 30, "average_elapsed_time": 25},
{"text_size": 2000, "pattern_size": 40, "average_elapsed_time": 21},
{"text_size": 2000, "pattern_size": 50, "average_elapsed_time": 16},
{"text_size": 3000, "pattern_size": 10, "average_elapsed_time": 18},
{"text_size": 3000, "pattern_size": 20, "average_elapsed_time": 21},
{"text_size": 3000, "pattern_size": 30, "average_elapsed_time": 18},
{"text_size": 3000, "pattern_size": 40, "average_elapsed_time": 17},
{"text_size": 3000, "pattern_size": 50, "average_elapsed_time": 18},
{"text_size": 4000, "pattern_size": 10, "average_elapsed_time": 21},
{"text_size": 4000, "pattern_size": 20, "average_elapsed_time": 15},
{"text_size": 4000, "pattern_size": 30, "average_elapsed_time": 15},
{"text_size": 4000, "pattern_size": 40, "average_elapsed_time": 28},
{"text_size": 4000, "pattern_size": 50, "average_elapsed_time": 14},
{"text_size": 5000, "pattern_size": 10, "average_elapsed_time": 25},
{"text_size": 5000, "pattern_size": 20, "average_elapsed_time": 23},
{"text_size": 5000, "pattern_size": 30, "average_elapsed_time": 19},
{"text_size": 5000, "pattern_size": 40, "average_elapsed_time": 15},
{"text_size": 5000, "pattern_size": 50, "average_elapsed_time": 16},
]
# Convert the list of dictionaries to a DataFrame
df = pd.DataFrame(data)
# Plot the data
plt.figure(figsize=(10, 6))
# Create separate lines for each pattern size
for pattern_size in df['pattern_size'].unique():
subset = df[df['pattern_size'] == pattern_size]
plt.plot(subset['text_size'], subset['average_elapsed_time'], label=f'Pattern size: {pattern_size}')
plt.xlabel('Text Size')
plt.ylabel('Average Elapsed Time (ms)')
plt.title('KMP Algorithm Time Complexity - O(n+m)')
plt.legend()
plt.grid(True)
plt.show()