Luiz Leonardo: "Muito obrigado Luciano. Provavelmente é isso mesmo."
Sim, é isso. Obrigado, Luciano.
Luiz Leonardo: "Nesse aspecto teriamos um ganho de tempo de "n*m" para "n.logn"..."
Uma pequena correção: o ganho de tempo é de O(n * m) para O(n * log m), onde n é o número de tarefas e m o de máquinas.
Luiz Leonardo: "Para valores pequenos de "n", como os do exercício, não sei se o ganho de tempo seria justificável, levando em consideração a perda de concisão e clareza do EP."
Só haverá ganho para valores grandes de m. Num caso como o do exemplo do enunciado (valores de n e m pequenos), o uso de um min-heap não traz nenhuma vantagem.
Note, entretanto, que o problema do escalonamento não restringe os valores de n e de m. Seu programa (pelo menos a parte que implementa o algoritmo de Graham) deve rodar para instâncias grandes do problema do escalonamento. A ressalva (só "a parte que implementa o algoritimo de Graham") é porque para instâncias grandes a busca exaustiva leva um tempo proibitivo: na prática ela não acaba nunca! Isso acontece mesmo para instâncias de tamanho moderado. Mas a o algoritmo de Graham deve rodar bem para instâncias grandes (com os números de tarefas e de máquinas na casa dos milhares ou milhões).
Luiz Leonardo: "Professor. Haverá perda de nota caso a função Graham seja feita por busca interativa?"
Sim.
Forum