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 length of islands in initialisation.
__init__ should have worst case complexity O(Nlog(N)) or less
select_islands should have worst case complexity O(N) or less, and a best case complexity of O(log(N)) or less.
select_islands_for_crew_numbers has a worst case complexity of O(C×N), where C is the length of crew_numbers.
update_island should have worst case complexity O(log(N)) or less
from island import Island
import heapq
class Mode1Navigator:
"""
Student-TODO: short paragraph as per https://edstem.org/au/courses/12108/lessons/42810/slides/294117
"""
def __init__(self, islands, crew):
"""
Student-TODO: Best/Worst Case
"""
self.islands = islands
self.crew = crew
def select_islands(self):
"""
Student-TODO: Best/Worst Case
"""
actions = []
remaining_crew = self.crew
island_heap = []
for island in self.islands:
if island.marines > 0:
heapq.heappush(island_heap, (-island.money / island.marines, island))
while remaining_crew > 0 and island_heap:
_, island = heapq.heappop(island_heap)
pirates = min(remaining_crew, island.marines)
money_earned = min((pirates * island.money) / island.marines, island.money)
actions.append((island, pirates))
remaining_crew -= pirates
return actions
def select_islands_from_crew_numbers(self, crew_numbers):
"""
Student-TODO: Best/Worst Case
"""
money_earned = []
for crew_size in crew_numbers:
self.crew = crew_size
actions = self.select_islands()
total_money = sum(pirates * island.money / island.marines for island, pirates in actions)
money_earned.append(total_money)
return money_earned
def update_island(self, island_name: Island, new_money: float, new_marines: int) -> None:
"""
Student-TODO: Best/Worst Case
"""
for i, orig_island in enumerate(self.islands):
if orig_island == island_name:
self.islands[i].money = new_money
self.islands[i].marines = new_marines
break
Modern Systems Analysis And Design
ISBN: 9780134204925
8th Edition
Authors: Joseph Valacich, Joey George