O que significa dizer "Assintoticamente mais eficiente"?

12

O que significa quando dizemos que um algoritmo é assintoticamente mais eficiente que Y ?XY

  • será uma escolha melhor para todas as entradas.X
  • será uma escolha melhor para todas as entradas, exceto as pequenas.X
  • será uma escolha melhor para todas as entradas, exceto as grandes.X
  • será uma escolha melhor para pequenas entradas.Y

O link para esta pergunta está aqui.

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/


Eu pensei que um algoritmo mais assintoticamente eficiente deveria funcionar para todas as entradas, mas não estou entendendo o motivo por trás de "Ele funciona para todas as entradas, exceto as pequenas".

Garrick
fonte
entrada grande expõe o gargalo da garrafa no algoritmo. É o que eu colocaria em termos de engenharia.
Apiwat Chantawibul

Respostas:

14

Primeiro, ambos os algoritmos "funcionam" para todas as entradas. A questão é sobre desempenho.

As respostas para essa pergunta são meio ruins. Uma maneira de dizer que um algoritmo é assintoticamente mais eficiente que outro é se houver algum tamanho de entrada (específico do problema), de modo que, para qualquer tamanho de entrada maior, o algoritmo mais eficiente execute menos "etapas computacionais", geralmente por alguma medida abstrata, por exemplo número de comparações.

X

5O(n2)O(nlgn)5cnlgn+o(nlgn)co(nlgn)neste exemplo - torna o algoritmo quase certamente completamente inviável para praticamente qualquer problema real. O que quero dizer com "completamente inviável"? Quero dizer, a morte por calor do universo acontecerá muitas vezes antes que o algoritmo seja concluído. No entanto, para entradas "grandes" adequadamente, será mais rápido que o tipo de bolha. O que quero dizer é que quase certamente não é fisicamente possível escrever de forma alguma uma entrada "adequadamente grande", muito menos computá-la.

XY

cc

Derek Elkins deixou o SE
fonte
2

O que as pessoas geralmente querem dizer quando dizem algo assim é:

TATBABTAo(TB)

X

Em particular, nenhuma das afirmações que você propõe segue, mesmo que as pessoas sugiram a segunda.

Infelizmente, a comunidade mais ampla de pessoas que lidam com algoritmos adota terminologia que se aproxima do vazio por uma questão de simplicidade. (Fazer declarações precisas e úteis sobre algoritmos é difícil!)

Você pode estar interessado em nossas perguntas de referência .


Diz-se que um algoritmo X é assintoticamente melhor que Y se X leva um tempo menor que y para todos os tamanhos de entrada n maiores que um valor n0 onde n0> 0.

Observe como isso não éTA(n)=n+1TB(n)=n

Eu recomendo que você aprenda ciência da computação com recursos do CS, não com programadores que já leram sobre coisas na Wikipedia uma vez. (Sim, isso é duro, mas já vi muitas falsidades propagadas nos círculos de programadores, mesmo no SO).

Rafael
fonte
2

"Assintoticamente mais eficiente" significa "mais eficiente para todos os problemas acima de um determinado tamanho". Não diz qual é o "tamanho certo" e não diz o que acontece antes desse "tamanho certo".

Portanto, todas as respostas, exceto a segunda, estão claramente erradas, porque "Assintoticamente mais eficiente" não diz nada sobre pequenos tamanhos de entrada. Mas o segundo também é problemático.

103010301040

Na prática, geralmente é uma boa idéia verificar para qual tamanho de entrada um algoritmo assintoticamente melhor é realmente mais rápido e qual o tempo necessário para entradas onde é mais rápido, e às vezes um algoritmo será mais rápido apenas para tamanhos de problemas que não podem praticamente seja resolvido de qualquer maneira. Se o algoritmo A vencer o algoritmo B, mas apenas para problemas em que cada um deles1015

gnasher729
fonte