5
Estoy trabajando en un problema de tarea y tengo algunas dificultades para crear una solución O (n * logn). Necesito escribir una función que tome una matriz preordenada y un valor para buscar. Entonces necesito encontrar si alguno de los dos elementos de la matriz suma para igualar ese valor.Encontrar si dos elementos en una matriz preordenada suman un valor igual a
Necesito crear algoritmos O (n) y O (n * logn) para esto.
El O (n) fue fácil de crear; sin embargo, tengo dificultades para crear el algoritmo O (n * logn) sin agregar ningún código gratuito que no ayude a resolver el problema. Si alguien pudiera darme algunos consejos sobre lo que podría extrañar, sería apreciado.
¿Cómo lo hizo en O (n)? – letsc
@letsc: use dos índices a y b; inicializar con a = 1 y b = n. Verifique la suma de los elementos en los índices a y b. Si la suma es tu objetivo, detente, encontraste los elementos. Si la suma es menor, aumente a; si es más bajo, disminuye b. Cuando a = b, detener, no hay elementos que coincidan. Debido a que los elementos están ordenados, solo omitirá pares que usted sabe que no son candidatos. – Joubarc