Me estoy preparando para una entrevista técnica y una de mis preguntas de práctica es el número K-ésimo más pequeño. Sé que puedo ordenar el tiempo O(n * log(n)) y usar un montón para O(n * log(k)). Sin embargo, también sé que puedo particionarlo (similar a Quicksort) para un caso promedio de O(n).

La complejidad de tiempo promedio calculada real debe ser:

Revisé dos veces esta matemática usando WolframAlpha, y está de acuerdo.

Así que codifiqué mi solución y luego calculé la complejidad del tiempo promedio real en conjuntos de datos aleatorios. Para valores pequeños de n, está bastante cerca. Por ejemplo, n=5 podría darme un valor real de alrededor de 6,2 cuando espero alrededor de 5,7. Este error un poco más es consistente.

Esto solo empeora a medida que aumento el valor de n. Por ejemplo, para n=5000, obtengo alrededor de 15 000 para mi complejidad de tiempo promedio real, cuando debería ser un poco menos de 10 000.

Entonces, básicamente, mi pregunta es ¿de dónde vienen estas iteraciones adicionales? ¿Mi código es incorrecto o son mis matemáticas? Mi código está a continuación:

 import java.util.Arrays; import java.util.Random; public class Solution { static long tc = 0; static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static int kMin(int[] arr, int k) { arr = arr.clone(); int pivot = pivot(arr); if(pivot > k) { return kMin(Arrays.copyOfRange(arr, 0, pivot), k); } else if(pivot < k) { return kMin(Arrays.copyOfRange(arr, pivot + 1, arr.length), k - pivot - 1); } return arr[k]; } static int pivot(int[] arr) { Random rand = new Random(); int pivot = rand.nextInt(arr.length); swap(arr, pivot, arr.length - 1); int i = 0; for(int j = 0; j < arr.length - 1; j++) { tc++; if(arr[j] < arr[arr.length - 1]) { swap(arr, i, j); i++; } } swap(arr, i, arr.length - 1); return i; } public static void main(String args[]) { int iterations = 10000; int n = 5000; for(int j = 0; j < iterations; j++) { Random rd = new Random(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = rd.nextInt(); } int k = rd.nextInt(arr.length - 1); kMin(arr, k); } System.out.println("Actual: " + tc / (double)iterations); double expected = 2.0 * n - 2.0 - (Math.log(n) / Math.log(2)); System.out.println("Expected: " + expected); } }