Cenário mais baixo e pior caso

Question

Sabemos que o limite inferior é a quantidade mínima de trabalho necessária para resolver um problema.Então, para um determinado problema diz que X tem o melhor algoritmo (o algoritmo mais eficiente para resolver esse problema) dizer algoritmo Y, então a eficiência inferior limitada calculada a partir desse algoritmo Y é o menor tempo que esse problema x pode ser resolvido.Então, por que calculamos a menor eficiência encadernada para esse algoritmo na pior das hipóteses?Por que não na melhor entrada de caso?Quero dizer, o limite inferior é a quantidade mínima de trabalho que, portanto, ocorre no melhor cenário de caso.Toda vez que vejo um problema de algoritmo de árvore de decisão para resolver o limite inferior de algum algoritmo de classificação, a palavra usual é sempre mencionada "o pior caso menor é Blah Blah Blah", que me confunde tanto!Alguém por favor consertar meu entendimento :(.

Answer 1

Ao analisar os algoritmos, faz pouco sentido considerar o cenário melhor caso, pois é muito trivial e não é muito informativo.

Você pode se convencer de que quase todos os algoritmos podem ser adaptados para ter uma complexidade melhor caso de $ O (n) $ , onde $ n $ é o tamanho da entrada, simplesmente executando uma verificação preliminar que verifica se a instância de entrada pertencer a algumas instâncias para as quais a solução é trivial.

Apenas para dar um exemplo concreto: o melhor caso para cada algoritmo de classificação pode ser feito $ O (n) $ Se você acabou de verificar se a sequência de entrada de números já está classificado.

O foco é muitas vezes na pior complexidade. Depois de decidir que você deseja comparar algoritmos em relação à sua pior complexidade, também faz sentido perguntar a rapidez com que um problema pode ser resolvido.

Geralmente é impossível dar uma ligação afiada ao tempo necessário para resolver um problema, portanto, um procura limites superior e inferior.

Um limite superior de $ o (f (n)) $ informa que há algum algoritmo que resolve o problema no recipiente de matemática $ O (f (n)) $ tempo de pior caso.

Um limite inferior da $ \ ômega (g (n)) $ informa que nenhum algoritmo concebível pode levar $ o (g (n)) $ tempo para resolver o problema.

apenas para ser claro: um limite inferior no tempo necessário para resolver um problema é expresso como uma função do tamanho da entrada $ n $ e é o menor valor de trabalho necessário para resolver Todas as instâncias de tamanho $ n $ . Intuitivamente (não uma definição formal) Você pode pensar nisso como $ \ min_ {\ in \ mathcal {}} \ max_ {i \ in \ mathcal {i} _n} t (A, i) $ onde $ \ mathcal {a} $ é o conjunto de todos os algoritmos possíveis que resolvem seu problema, $ \ mathcal {i} _n $ é o conjunto de todas as instâncias de tamanho $ n $ e $ t (a, i) $ é o tempo necessário por $ a \ in \ mathcal {a} $ para resolver a instância $ i \ in \ mathcal {i} _N $ .

O que você parece ter em mente é $ \ min_ {\ in \ mathcal {}} \ min_ {i \ in \ mathcal {i} _n} t ( A, i) $ .

Um limite inferior para um problema é útil estabelecer como "difícil" esse problema é resolver (problemas que exigem mais tempo para resolver são mais difíceis, isso faria pouco sentido se analisássemos as instâncias mais fáceis) e Meça até onde um algoritmo é de ser ideal. Por exemplo, Merge Classificar resolve o problema de classificação no tempo ideal de tempo, porque seu tempo de execução (assintoticamente) corresponde à $ \ ômega (n \ log n) $ inferior o problema de triagem (no modelo baseado em comparação).

Answer 2

"limite inferior" pode ser aplicado para cada cenário e individualmente não significativo!(Bipo inferior do quê?) Ao analisarmos o pior cenário, a maior parte do tempo, a complexidade de um algoritmo, portanto, "limite inferior" é aplicado para o pior cenário (não o melhor caso). Em outras palavras, à medida que a complexidade do tempo está explicando para o pior cenário, o "limite inferior" para a complexidade de tempo será aplicado ao pior cenário.