File size: 2,747 Bytes
f8a39f0 | 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | def estimate_complexity(features: dict) -> dict:
"""
Estimates time complexity using heuristic rules
based on static code features.
"""
result = {
"time_complexity": "O(1)",
"explanation": "No loops or recursion were detected, suggesting constant time operations."
}
max_depth = features.get("max_loop_depth", 0)
# ----- BFS/DFS Pattern -----
if features.get("bfs_pattern") or features.get("dfs_pattern"):
return {
"time_complexity": "O(V + E)",
}
# ----- Binary search heuristic -----
if features.get("binary_search_pattern"):
result["time_complexity"] = "O(log n)"
return result
# ----- Dynamic Programming -----
if features.get("dp_pattern"):
result["time_complexity"] = "O(n) or O(n²)"
# result["explanation"] = (
# "Dynamic programming detected. Complexity depends on the number "
# "of states and transitions."
# )
return result
# ----- Merge Sort -----
if features.get("merge_sort_pattern"):
return {
"time_complexity": "O(n log n)"
}
# ----- Quick Sort -----
if features.get("quick_sort_pattern"):
return {
"time_complexity": "O(n log n) average, O(n²) worst-case"
}
# ----- Recursion Heuristics -----
if features["recursion"]:
if features.get("divide_and_conquer"):
result["time_complexity"] = "O(n log n)"
return result
if features["recursive_call_count"] >= 2:
result["time_complexity"] = "O(2^n)"
return result
result["time_complexity"] = "O(n)"
return result
# ----- Sorting Algorithms -----
if features.get("bubble_sort_pattern"):
return {
"time_complexity": "O(n²) worst-case (O(n) best-case if optimized)"
}
if features.get("insertion_sort_pattern"):
return {
"time_complexity": "O(n²) worst-case (O(n) best-case for nearly sorted input)"
}
# ----- Sliding Window -----
if features.get("sliding_window_pattern"):
return {
"time_complexity": "O(n)"
}
# ----- Heap-Based -----
if features.get("heap_pattern"):
return {
"time_complexity": "O(n log n) or O(log n) per operation"
}
# ----- Iterative Heuristics -----
if max_depth == 1:
result["time_complexity"] = "O(n)"
return result
if max_depth >= 2:
result["time_complexity"] = f"O(n^{max_depth})"
return result
return result
|