Can you check if all the methods have the intended complexities and if they don't change them
Question:
Can you check if all the methods have the intended complexities and if they don't change them so that they do.
Intended Complexities
Let N be the current number of islands with non-zero money, and C be the number of captains participating in the Davy Back Fight.
add_islands should have a worst case complexity of at most O(N+I), where I is the length of islands.
simulate_day should have a worst case complexity of at most O(N+Clog(N)).
from island import Island
import heapq
class Mode2Navigator:
"""
Student-TODO: short paragraph as per https://edstem.org/au/courses/12108/lessons/42810/slides/294117
"""
def __init__(self, n_pirates: int) -> None:
"""
Student-TODO: Best/Worst Case
"""
self.n_pirates = n_pirates
self.islands = []
def add_islands(self, islands: list[Island]):
"""
Student-TODO: Best/Worst Case
"""
self.islands.extend(islands)
def potential_score(self, island, crew):
m = min(island.money, island.money * crew / island.marines) if island.marines > 0 else island.money
c_left = crew - min(crew, island.marines)
return 2 * c_left + m
def simulate_day(self, crew: int):
"""
Student-TODO: Best/Worst Case
"""
decisions = []
for _ in range(self.n_pirates):
if not self.islands:
decisions.append((None, 0))
continue
# Use a max-heap to efficiently find the island with the best potential score
island_scores = [(-self.potential_score(island, crew), island) for island in self.islands]
heapq.heapify(island_scores)
# Get the island with the best potential score
best_score, best_island = heapq.heappop(island_scores)
# Determine the crew to be sent
c_to_send = min(crew, best_island.marines)
# Add to the decisions
decisions.append((best_island, c_to_send))
# Update island's state
best_island.money -= min(best_island.money, best_island.money * c_to_send / best_island.marines)
best_island.marines -= c_to_send
# If island is emptied, remove it from the list
if best_island.marines == 0:
self.islands.remove(best_island)
return decisions
Modern Systems Analysis And Design
ISBN: 9780134204925
8th Edition
Authors: Joseph Valacich, Joey George