¿Cuál es la complejidad de O(1/n) en comparación con O(n)?

¿O(1/n) crece más rápido que O(1)? Estoy estudiando la complejidad del tiempo y no estoy seguro de cómo deducir la respuesta a esta pregunta.

Solución del problema

Una complejidad de O(1/n)significaría que cuantos más datos proceses, más rápido es el algoritmo... Bastante difícil de creer, primero, y segundo, hagamos matemáticas: el límite de 1/x cuando x va a +INF es cero....

¿Entonces el algoritmo resolvería instantáneamente el problema? Oye, olvidémonos de la computación cuántica, ¡encontramos algo mejor!:)

Deja de bromear: tal complejidad no existe. Porque 1/nes una función monótona decreciente. Las complejidades son funciones monótonas crecientes; en el mejor de los casos, es O(1), lo que significa un tiempo constante sea cual sea la cantidad de datos. Ni siquiera es una complejidad tan común para un algoritmo, de hecho, incluso si es bastante frecuente para ciertas operaciones / manipulaciones.

Por ejemplo, recuperar el encabezado de una lista enlazada estándar sí lo es O(1), incluso si la lista está vacía o si contiene todos los datos posibles del Universo (si fuera almacenable...), porque el encabezado de la lista es lo que se almacena para acceder a él. Es lo mismo para todas las operaciones que involucran solo el intercambio de punteros/manejadores exclusivamente, todos los accesos directos (como el []operador de la mayoría de las matrices), etc. pero la mayoría de los algoritmos no tienen una complejidad tan agradable.

Pero incluso una copia simple (profunda) es O(n)... La mayoría de las búsquedas en un almacenamiento están en O(log2(n)). La mayoría de los tipos están en O(n.log2(n)). La mayoría de las comparaciones cruzadas están en O(n²). Todas estas funciones son (estrictamente) crecientes. Todas estas funciones tienden a infinito cuando n también tiende a infinito.