Lectura de código real

Leer un fragmento generado

Texto

función más_cercanos(puntos, q, k):    resultado ← array vacío    repetir k veces:        ordenar(puntos, por distancia a q)        agregar(resultado, quitar_primero(puntos))    devolver resultado

Suponiendo que ordenar cuesta O(n log n) en cada llamada, ¿qué patrones tiene más_cercanos(puntos, q, k) y cuánto cuesta con n puntos?Contiene en un bucle: O(k × n) comparaciones; basta cambiar el array resultado por un conjuntoEs O(n log n): ordena una sola vez y toma los k primeros, así que no hay nada que revisarOrdenar en cada iteración, O(k × n log n); el arreglo es guardar las distancias en una tabla hashOrdenar en cada iteración y quitar el primero de un array: O(k × n log n); un heap de tamaño k basta