Algoritimo log n ? Logarítmica

Olá pessoal!

Alguém teria como indicar algum livro ou dar um exemplo do que seria um algoritmo Log n em java, tenho procurado explicações mas só encontrei exemplos matemáticos com explicações confusas, obrigado!!!

Essa parte de análise de complexidade é algo foda mesmo… MUITA matemática.
Você quer o que de uma função log(N) ? A função propriamente dita? Caça na documentação do Java que tem uns exemplos (algumas funções que eles garantem log(N) no caso médio, no TreeSet tem) aí c ve no source. Mas ainda assim não entendi sua dúvida…

Oi… eu precisava criar um algorítimo (FOR por exemplo) que seja um algoritmo Logarítmica para avaliação de desempenho em tamanhos de vetores diferentes ai queria encontrar ou ter uma ideia de onde pesquisar algorítimos que já usem a função logarítmica ou uma ideia mais direta e não apenas matemática da questão… obrigado!

Complexidade de algoritmos

Quando alguém fala que um algoritmo é O(log n), ele quer dizer o seguinte: a quantidade de operações básicas necessárias (ou o tempo) é proporcional a log n, onde n é um parâmetro que indica o tamanho do problema. E o que é “log n”? É o logaritmo de n, mas não precisa ser na base 10 ou na base “e”. Pode ser, por exemplo, na base 2. É que para mudar a base do logaritmo basta multiplicá-lo por uma constante, e para a parte de complexidade de algoritmos, multiplicar tudo por uma constante é irrelevante.

Por exemplo, diz-se que para encontrar um elemento em uma arvore binária perfeitamente balanceada, a complexidade do algoritmo é O (log n). Isso quer dizer o seguinte: para achar um elemento em uma árvore binária com 4 elementos (2 elevado a 2) é necessário fazer no máximo 2 comparações, ou seja, log de 4 na base 2 é 2.
Para fazer a mesma consulta em uma árvore com 1024 elementos (2 elevado a 10) é necessário no máximo fazer 10 comparações, ou seja, log de 1024 na base 2 é 10.

  1. A palavra é algoritmo (não tem acento nem esse i a mais, que é coisa de “adevogado”).

  2. Eu não entendi direito o que você precisa. Como assim “avaliação de desempenho em tamanhos de vetores diferentes”? Não entendi o seu problema.

Opa… valeu pela dica…
O problema basico verdade é algo do tipo implementar um algoritmo O(log n) ? Logarítmica e gerar informações para ?n? entradas distintas usando um for ou while…

Qual é o enunciado do exercício? Está faltando a parte principal (nunca você parte da complexidade de um algoritmo para resolver o problema. Você parte de um problema e acha o melhor algoritmo para resolvê-lo. Pode ser que você não tenha, para resolver o problema, um algoritmo O (log n) mas sim um O (n log n) (como é o caso de vários algoritmos para ordenação), por exemplo.

Não, nesse caso é só para implementar um (QUALQUER algoritmo) que use O(log n) …

Bom, procure um algoritmo que mexa com a estrutura de dados “Heap” , que usa vetores.

http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/heap.html
Leia isso direitinho.

Entendi… então a nível de inserção e remoção os algoritmos são considerados O (log n) mas tava lendo alguns outros métodos aplicados em estruturas heap como um sort ou uma varredura são consideradas O(n log n), seria possível criar uma logica para percorrer um heap que use O (log n) ? Obrigado!

Bom, você pode olhar este artigo aqui: ( http://en.wikipedia.org/wiki/Binary_heap )

(O artigo em português está muito incompleto. )

Para percorrer um heap em ordem crescente, o algoritmo tem pelo menos ordem O(n), não log (n), porque você precisa retornar todos os n elementos. Certo?

Opa obrigado! Mesmo assim estou com um pouco de dificuldades para criar esse algoritmo… mas estava lendo agora no site http://www.leepoint.net/notes-java/algorithms/big-oh/bigoh.html que falava que um Binary search sorted em um array/ArrayList gera um
O(log N) porem que requerem dados classificados(ordenados) então quer dizer que se eu der um sort e depois fizer uma busca por Binary search o conjunto geraria um algoritmo O(Log N) ou isso não é valido por serem 2 processos um para ordenar e outro para buscar?

No meu caso preciso fazer um algoritmo O(Log N) que sirva para percorrer vetores de tamanhos 10 - 100 - 1000 - 10000 e depois calcular com o System.nanoTime() o tempo para execução…

Obrigado!