Arquivo Discussoes de Programacao e Tecnologia Ola pessoal!
Estou com dificuldades de achar exemplos de algoritmos O(Log N), precisava 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 de cada um deles…
Alguém tem alguma dica de como montar de forma simples algum algoritmo desse tipo?
Obrigado!!
O algoritmo de busca binária em arrays ordenados ou em árvores binárias de busca é O(log n).
Exatamente o que eu ia responder. Mas o seu problema nao foi especificado completamente, seu arranjo é ordenado ? se sim concordo com davidbuzatto, caso contrario, vc terá que verificar alguns algoritmos de ordenação logn, como quicksort, mergesort…
Opa valeu David, tinha lido algo sobre isso já mas apenas em um site pouco conhecido, acabei montando o algoritmo com essa ideia… ordenei ele antes no main e depois fiz a busca binaria apesar de que acredito que o proprio algoritmo precisava ser O (Log n) na idéia do meu professor claro mas como tinha que enviar enviei com a idéia da busca binaria mas mesmo assim vou continuar dando uma olhada no caso que você falou Diego teriam algoritmos como Quicksort ou Mergesort em O (Log n)? Ou isso seria mais algo a se implementar?
Pergunto pois vi em um site que classificava esses dois como O (n Log n)…
Obrigado!
diegohsi, Magesort ou Quicksort ordenam em O(N * LogN).