Algoritmo para encontrar o primeiro inteiro maior com o-pequeno (n) complexidade

votos
0

Eu preciso escrever um algoritmo, que vai encontrar o primeiro número inteiro, que é maior do que x em uma matriz classificada, onde inteiros podem repetir. O algoritmo deve ter a complexidade de O (n), onde o é pequena. O que é a diferença entre os algoritmos com O (n) um O (n) dificuldade?

Publicado 20/10/2018 em 13:58
fonte usuário
Em outras línguas...                            


3 respostas

votos
2

Você pode usar método de pesquisa binária para encontrar o primeiro maior inteiro x. Seria no O(log(n)) = small_o(n).

Respondeu 20/10/2018 em 14:14
fonte usuário

votos
1

Como as pessoas têm apontado diante de mim, você quer fazer uma pesquisa binária. Este post inclui exemplo de código:

Em python isso é mais fácil com a função bisect: https://docs.python.org/2/library/bisect.html

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError
Respondeu 20/10/2018 em 14:42
fonte usuário

votos
1

Aqui é um muito bom e na explicação profundidade de Big-O vs pouco-o a notação: Diferença entre Big-O e Little-O Notation

O algoritmo mais simples, mas eficiente é Binary Search como @OmG mencionado, e aqui está o link para começar: https://en.wikipedia.org/wiki/Binary_search_algorithm

A idéia é bastante simples: basta comparar o número que você pesquise com o elemento do meio da matriz, se o meio é menor, então o seu número é óbvio que você precisa encontrar na metade direita, ... metade de outra forma esquerda. Você pára quando há apenas um elemento.

Respondeu 20/10/2018 em 14:22
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more