Um algoritmo ótimo é aquele que consegue resolver um determinado problema usando o mínimo de recursos possíveis. Porém, entramos aqui numa seara que acabe gerando não uma única opção ótima, mas uma curva de várias possibilidades de ótimos.
Por exemplo, o bitonic merge sort é mais eficiente ou menos eficiente do que um merge sort tradicional? Se for computado o tempo que se demora para que o algoritmo termine de se executar, então o bitonic merge sort é melhor: ele executa em menor tempo. Porém, ele só consegue essa melhoria fazendo mais computações: então ele consome mais energia.
Ele consegue fazer mais computações em menos tempo por conta de paralelismo.
Também tem outros aspectos: merge sort é um algoritmo de ordenação estável, mas o bitonic merge sort não é.
Então, como em diversos outros problemas de otimização, precisamos entender o que queremos otimizar e quais as restrições fornecidas. Por exemplo, se existisse uma quantidade quadrática de núcleos de processamento rodando, seria possível saber em O(log n)
qual o menor número.
Agora, seu professor disse que esse algoritmo é ótimo, mas será que ele é ótimo sempre para saber qual o mínimo em uma coleção de dados? A resposta é: não, existem casos em que as restrições do problema dizem que pode haver outro algoritmo mais eficiente.
Por exemplo, se o vetor estiver previamente ordenado, o algoritmo ótimo seria O(1)
com vet[0]
. Apesar de ser um caso estranho para esse problema (pegar o mínimo), essa circunstância (vetor ordenado) é comum de acontecer em outros problemas. Por exemplo, saber se um elemento aparece em um vetor. Se não houver garantia de ordenação, é necessário verificar todos os elementos da lista, 1 a 1, para garantir que o dado procurado realmente não esteja lá. Agora, se por acaso o problema já fornece um vetor ordenado, procurar por um elemento agora precisa de uma quantidade logarítmica, um algoritmo chamado de busca binária.
Outro ponto de saber se um algoritmo é ótimo é relativo a restrição de computação dele. Por exemplo, esse algoritmo é ótimo em tempo para coisas monoprocessadas. Eventualmente podemos ter mais de 2 núcleos de processamento disponíveis, então poderíamos dividir a carga de processamento pela metade, usando (de grosso modo) a mesma quantidade de processamento porém a metade do tempo.
Agora, sobre as respostas diretas das perguntas:
O que é um algoritmo ótimo?
É aquele algoritmo que, para o problema em questão, consome o mínimo de determinado recurso.
Por que esse algoritmo é ótimo?
Porque não há como fazer menos computações em um ambiente monoprocessado, e também não há como usar menos variáveis.
Outras possibilidades de se fazer um outro algoritmo para esse problema (identificar o menor elemento em um vetor não trivialmente vazio) ocasionaria em mais computações realizadas, ou então usar mais memória.
Um exemplo seria tratar especialmente a primeira vez que se entra no laço:
int min = 0;
for (int i = 0; i < n; i++) {
if (i == 0) {
min = v[i];
} else {
if (v[i] < min) {
min = v[i];
}
}
}
Note que aqui eu estou colocando uma condição a mais em cada repetição, que é verificar se estou no primeiro elemento. Isso se torna desnecessário porque o algoritmo fornecido já trata trivialmente o primeiro elemento.
Outra alternativa (ainda pior em termos de desempenho, na minha visão) seria trabalhar com Integer
(Integer min = null
), sendo o primeiro caso identificado como sendo min == null
:
Integer min = null;
for (int i = 0; i < n; i++) {
if (min == null) {
min = v[i];
} else {
if (v[i] < min) {
min = v[i];
}
}
}
Uma possível vantagem desse usando o Integer
só seria possível enxergar em uma situação: caso seja possível informar um tamanho 0 para o tamanho do vetor (indicado por n
). Nesse caso, o nulo significa que não há mínimo. Porém seria muito mais eficiente fazer assim:
Integer min;
if (n == 0) {
min = null;
} else {
int otherMin = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < otherMin) {
otherMin = v[i];
}
}
min = otherMin;
}
Outro ponto que é menos ótimo que o proposto pelo seu professor por uma execução:
int min = vet[0];
for (int i = 0; i < n; i++){
if (min > vet[i]){
min = vet[i];
}
}
Essa alternativa verifica a posição 0 que trivialmente já está na variável min
no começo da execução, portanto isso é feito à toa.
Consigo pensar ainda em mais duas alternativas:
int min = v[0];
for (int i = 1; i < n; i++) {
min = v[i] < min? v[0]: min;
}
Nessa alternativa há sempre n
atribuições e n
comparações, perdendo então na quantidade de atribuições feitas (que no melhor caso do algoritmo original é apenas a primeira).
A última alternativa seria começar com int min = Integer.MAX_VALUE;
e percorrer a lista inteira.
E como determinar se outros algoritmos são ótimos?
Vai depender muito de cada problema e quais os modelos computacionais usados. Normalmente se pensa em monoprocessadores, então talvez isso possa ser levado como uma restrição a priori. Em outros casos, devemos levar em consideração que a computação pode ser feita de maneira distribuída. Também precisamos saber o que queremos otimizar.
Existem problemas que podemos resolver usando memória adicional, porém em menos tempo. Existem também situações em que se devem responder diversas instâncias do mesmo problema, então podemos fazer um processamento inicial e reaproveitar a resposta "aprendida" em diversas vezes que o problema for perguntado. Por exemplo, podemos usar o crivo de Eratóstenes para determinar se o número é ou não primo, mas para executar todo o crivo para responder se 15 é primo é gastar muito processamento.
Tem casos em que se precisa economizar o máximo de memória possível, por mais que isso signifique gastar mais tempo de processamento.
Podemos tentar simplificar, falando sobre "ótimo" como sendo aquele algoritmo em um ambiente monoprocessado executar em menos tempo. Infelizmente, para se provar isso, precisamos de algum modo esgotar todas as possibilidades de algoritmos possíveis. Existem casos em que é possível fazer isso, normalmente para problemas na classe P. Mesmo com essas limitações, não consigo imaginar um método geral para fazer isso. No máximo, consigo pensar apenas em como comparar dois algoritmos.