O que significa o 'limite superior' no contexto do BigO?

5

Meu professor de ciências da computação diz que o Big O tem um limite superior, mas não um limite inferior. Quando olho para um gráfico de um algoritmo mapeado usando BigO, não há um limite superior. O limite superior continua para sempre. Então, o que significa dizer que existe um limite superior no contexto do BigO?

    
por chopper draw lion4 26.09.2014 / 21:18
fonte

2 respostas

9

O BigO é, simplesmente, uma medida da complexidade do algoritmo. Na melhor das hipóteses, até mesmo o pior algoritmo pode ser concluído em uma operação / iteração. No entanto, diferentes operações têm diferentes complexidades de média e pior caso. Estas complexidades de pior caso podem ser consideradas o limite superior.

Então, como podemos descobrir o limite superior?

Um algoritmo terá diferentes durações de corrida com base no tamanho dos dados que está manipulando. Como exemplo, vamos considerar uma estrutura de dados simples, que poderia ser implementada de várias maneiras (vamos usar uma matriz) e decidimos que queremos procurar na estrutura por um pedaço de dados. O número de operações que você precisa fazer será baseado no tamanho da coleta de dados. Vamos supor que existam n elementos na estrutura.

Um array típico, na pior das hipóteses, itera toda a coleção para isso, o que significa que você executará até n operations, resultando em O(n) complexity, portanto, você tem um limite superior de n .

Vamos supor que os dados estejam classificados: agora você pode realizar uma pesquisa binária, resultando em log(n) operações, reduzindo a complexidade com um limite superior de O(log(n)) . Ele ainda poderia ser concluído em uma operação, e se n abordasse um número infinito, a complexidade se aproximaria do tempo de execução infinito. Isso é provavelmente o que você estava vendo na aula. Diferentes complexidades de algoritmo abordam este nível de execução infinito em diferentes taxas (n! & Nbs; n ^ 2 > n > log (n) > 1).

Edit: De acordo com os comentários, deve-se notar que uma mudança na quantidade de dados também será refletida por uma mudança no tempo de execução com base na complexidade. Os algoritmos O (1) não serão alterados, os logarítmicos serão alterados de maneira logarítmica, os algoritmos lineares linearmente, etc. Essencialmente, dobrar a quantidade de dados pode NÃO duplicar seu tempo de execução. Você pode quadruplicá-lo ou aumentá-lo por um fator menor ou maior.

Para um exemplo mais complexo, é necessário mais trabalho para descobrir a complexidade, mas esta é a ideia geral:

O Limite Superior da complexidade de um algoritmo descreve como o tempo de execução do algoritmo muda com uma mudança na quantidade de dados sendo processados na operação, o que significa que um algoritmo mais complexo um tempo cada vez maior (muitas vezes não linearmente) para executar à medida que a quantidade de dados é aumentada.

    
por 26.09.2014 / 21:35
fonte
1

O pior cenário nos dá um limite superior no desempenho. A análise do pior caso de um algoritmo garante que ele nunca terá um desempenho pior do que o que determinar.

    
por 18.01.2016 / 17:37
fonte