O(nlogn) solución (todavía no estoy claro por qué usted está buscando una solución cota más baja . Es lo mismo que acaba de hacer una comprobación exhaustiva, y luego simplemente ejecutar un bucle nlogn para asegurarse de la cota inferior No es muy difícil. Creo que debes querer decir el límite superior):
Encuentra el único punto candidato válido promediando todos los puntos. Es decir. sumando sus coordenadas y dividiendo por el número de puntos. Si tal k existe, este es. Si no existe tal k, veremos que el punto encontrado no es válido en el paso final.
Cree una nueva matriz (conjunto) de puntos, donde cambiamos nuestros ejes para que se centren en el punto k. Es decir. si k = (x k, y k), un punto (x, y) se convertirá en (x-x k, y-y k). Ordene los puntos según la relación x/y la norma sqrt (x + y). Como muestra el siguiente paso, no importa cómo se realiza este tipo, es decir, cuál es el criterio principal y cuál el secundario.
Podríamos buscar el complemento de cada punto, o mejor, simplemente recorrer la matriz y verificar que cada dos puntos adyacentes sean de hecho complementos. Es decir. si esta es una solución, cada dos puntos complementarios en esta nueva matriz son de la forma (x, y) y (-x, -y) ya que recentramos nuestros ejes, lo que significa que tienen la misma proporción ("gradiente") y norma, y después del género, debe ser adyacente.
Si k no es válido, entonces hay un punto al que llegaremos en este recorrido, y descubrimos que su vecino no es de la forma correcta/complementaria ==> no existe tal k.
Tiempo =
O(n) para encontrar el candidato k +
O(n) para la construcción de la nueva matriz, ya que cada nuevo punto puede calcularse en O (1) +
O(nlogn) para el tipo +
O(n) para la verificación recorrido
= O(nlogn)
Realmente no entiendo su pregunta. Un algoritmo que encuentra un límite inferior¿Te refieres a un algoritmo * con * un límite inferior? ¿O una prueba de que dicho algoritmo * tiene * un límite inferior? – davin