Complejidad computacional de generar un vector aleatorio

Question

Soy nuevo en el concepto de complejidad computacional y trato de comprender el tema en profundidad. Pasé por algunas referencias mencionadas por algunas preguntas anteriores, sin embargo, tenía esta pregunta y no estoy seguro de si mi comprensión es correcta.

Quiero saber la complejidad de generar un vector aleatorio uniforme, sobre $[0, 1]$, de tamaño $N$ usando digamos un generador de números aleatorios en Python o Matlab.

Lo es $\mathcal{O}(N)$ porque estoy generando $N$ números aleatorios y la complejidad de generar cada uno de ellos es $\mathcal{O}(1)$ o es simplemente $\mathcal{O}(1)$?

Answer 1

No puede crear un número uniformemente aleatorio en $[0,1]$ en tiempo finito, porque eso requeriría una precisión infinita.

Probablemente eso no es lo que quieres. Probablemente desee generar un flotante aleatorio en el rango$[0,1]$. Luego tenemos que preguntarle qué suposiciones está dispuesto a hacer acerca de su generador de números pseudoaleatorios. Para muchos de ellos, probablemente sea razonable tratar la generación de un flotador aleatorio en ese rango como tomar$O(1)$hora. Si es así, puede crear un$N$-vector dimensional con $N$ llamadas a ese generador pseudoaleatorio, es decir, en $O(N)$ hora.

Consulte ¿Cómo crear el tiempo de ejecución de los algoritmos? , ¿Cómo se sabe qué notación de análisis de complejidad de tiempo usar? , ¿Existe un sistema detrás de la magia del análisis de algoritmos? y un buen libro de texto para una descripción general del análisis del tiempo de ejecución asintótico.