limite superior, um limite inferior

Question

O que significa para provar um limite superior ou limite inferior a um algoritmo?

Answer 1

Provando um meio encadernados superiores você tem provado que o algoritmo irá usar não mais do que algum limite em um recurso.

Provando um meio encadernados mais baixos você provaram que o algoritmo irá usar não menos do que algum limite em um recurso.

"Resource" neste contexto poderia ser tempo, memória, largura de banda, ou algo mais.

Answer 2

limites superior e inferior tem a ver com o mínimo eo máximo "complexidade" de um algoritmo (eu uso essa palavra deliberadamente uma vez que tem um significado muito específico na análise de complexidade).

Tomemos, por exemplo, o nosso velho amigo, o bubble sort. Em um caso ideal, onde todos os dados já estão ordenados, o tempo necessário é f (n), um dependente n função, o número de itens na lista. Isso é porque você só tem que fazer uma passagem do conjunto de dados (com zero swaps) para garantir a sua lista é ordenada.

Em um particularmente ruim caso em que os dados são ordenados na oposta à ordem que quiser, o tempo torna-se f (n ² ). Isso ocorre porque cada passagem move um elemento para a posição certa e você precisa n passes para fazer todos os elementos.

Nesse caso, os limites superiores e inferiores são diferentes, embora a complexidade big-O permanece o mesmo.

Como um aparte, o bubble sort é muito difamado (geralmente por boas razões), mas ele pode fazer sentido em certas circunstâncias. Na verdade, eu usá-lo em um aplicativo, onde a maior parte dos dados já são classificadas e apenas um ou dois itens tendem a ser adicionado ao mesmo tempo para o fim da lista. Para adicionar um item, e com uma espécie de bolha direcional reversa, você pode garantir a nova lista será classificada em uma passagem. Isso ilustra o conceito limite inferior.

Na verdade, você poderia fazer uma otimização do tipo bolha que define o limite inferior para f (1), simplesmente fornecendo um dado extra que indica se a lista é ordenada. Você deve definir isso depois de triagem e limpá-la ao adicionar um item ao final.

Answer 3

Seja qual for o obrigado (superior ou inferior), estamos sempre falando sobre a entrada de pior caso que podemos considerar. Por exemplo, na classificação, assumimos que o pior caso é uma lista de entrada indiferenciados.

O meu entendimento é que problemas tem um limite inferior. Por exemplo, podemos dizer que o limite inferior da classificação é baseada em comparação \ Omega (n log n); estamos fazendo há suposições sobre o que em particular comparação baseada-ordenação algoritmo que usamos. Seja qual for o algoritmo (merge sort, rápido tipo, etc), não podemos fazer melhor do que este ligado de \ Omega (n log n). limites inferiores nos dizer, intuitivamente, o quão difícil um determinado problema é.

Quando falamos de uma específica algoritmo , então falamos de limites superiores. Por exemplo, podemos dizer que o limite superior da bubble sort é O (n ^ 2) e o limite superior de merge sort é O (n log n). limites superiores, intuitivamente, nos dizer o quão bom um determinado algoritmo é a resolver o problema.