Alguém poderia me explicar como seria um método de complexidade O(1), ou seja, um método “Big O”?
O que torna um método em um Big O?
Obrigado!!
=)
Big O é uma notação referente à complexidade de um algoritmo qualquer (não necessariamente um método). Leia mais aqui : https://pt.stackoverflow.com/questions/56836/definição-da-notação-big-o/56842
Um exemplo de algoritmo de complexidade O(1) seria algo como :
int a = umArrayQualquer[6];
Veja mais exemplos em : https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
Abraço.
Na verdade, a instrução de criar um array pode ser O(n), depende da implementação da JVM. Isso porque depois da alocação, a implementação precisa de alguma forma definir o valor inicial de cada posição (que no caso de int é 0). Existem algoritmos para fazer isso em tempo constante, mas isso é um detalhe de implementação, já que a especificação da JVM não obriga que seja O(1).
Eu tenho quase certeza que a da HotSpot é O(n). Para testar, é só medir o tempo para criar int[1] e int[1000000].
Legal, isto eu entendi.
O que ainda não ficou muito claro é o que tornaria um método em Big O.
No exemplo citado, um ArrayList possui uma complexidade O(1) mas seria somente isso?
Se eu tenho uma classe Pilha com metodos Push e Pop, como implementaria estes métodos de tal forma que fossem O(1), seria somente fazendo uso de um ArrayList?
Obrigado!
Big O é uma notação que te dá uma noção de como o algoritmo escala no pior caso. Você consegue ter uma ideia de como o tempo de execução vai mudar em relação ao tamanho da(s) entrada(s). Um método não “se torna” Big O, essa é apenas a notação, a forma de análise de complexidade temporal.
Por exemplo, um algoritmo de ordenação de vetor que compara cada posição com todas as outras é O(n^2), porque o tempo de execução aumenta de forma quadrática em relação ao aumento do tamanho do vetor (n = tamanho do vetor).
O(1) está te dizendo que a execução do algoritmo independe do tamanho dos dados que ele opera. Não importa o quanto você aumente ou diminua os dados, a execução vai durar sempre o mesmo tempo.
(Des)empilhar um elemento em uma pilha é um exemplo de O(1).
Para que o método seja O(1) você precisa que eles não dependam do tamanho da estrutura. Você precisa pensar em uma maneira de não precisar percorrer a estrutura para executa-los.
1 curtida
SHOW!! Acho que agora ficou muito mais claro.
Muito obrigado!!!
ajudou horrores!
Agradeço a você também, LVBarbosa.
O código que postei é o acesso à uma posição do array - que é O(1) - , não a criação do array, que pode ser O(n) como você explicou. É o primeiro exemplo no link que postei. Nem foquei na solução ser em Java (este código em específico funciona em C também, por exemplo).
O exemplo que citei fala de um array convencional, não um ArrayList. É importante ter essa distinção porque o ArrayList pode fazer coisas de forma diferente.
Abraços.
.
1 curtida
Verdade, troquei as bolas. De qualquer forma, fica o conhecimento.