big-o - for - big omega
¿Qué significa "O(1) access time"? (15)
Básicamente, O (1) significa que su tiempo de cálculo es constante, mientras que O (n) significa que dependerá linealmente del tamaño de la entrada, es decir, el bucle a través de una matriz tiene O (n) - solo bucle -, porque depende del número de artículos, mientras calcula el máximo entre números ordinarios tiene O (1).
Wikipedia podría ayudar también: http://en.wikipedia.org/wiki/Computational_complexity_theory
He visto que este término "O (1) tiempo de acceso" solía significar "rápidamente", pero no entiendo lo que significa. El otro término que veo con él en el mismo contexto es "O (n) access time". ¿Podría alguien explicar por favor de manera simple qué significan estos términos?
Ver también
Básicamente, significa que se necesita la misma cantidad de tiempo para buscar un valor en su colección, ya sea que tenga una pequeña cantidad de elementos en su colección o muchos (dentro de las limitaciones de su hardware).
O (n) significa que el tiempo que se tarda en buscar un elemento es proporcional al número de elementos en la colección.
Ejemplos típicos de esto son las matrices, a las que se puede acceder directamente, independientemente de su tamaño, y las listas vinculadas, que deben atravesarse en orden desde el principio para acceder a un elemento determinado.
La otra operación generalmente discutida es insertar. Una colección puede ser O (1) para acceso pero O (n) para inserción. De hecho, una matriz tiene exactamente este comportamiento, porque para insertar un elemento en el medio, debe mover cada elemento hacia la derecha copiándolo en la siguiente ranura.
Cada respuesta que responde actualmente a esta pregunta te dice que O(1) significa tiempo constante (lo que sea que pase con la medición, podría ser el tiempo de ejecución, el número de operaciones, etc.). Esto no es exacto
Decir que el tiempo de ejecución es O(1) significa que hay una constante c tal que el tiempo de ejecución está limitado por c , independientemente de la entrada. Por ejemplo, devolver el primer elemento de una matriz de n enteros es O(1) :
int firstElement(int *a, int n) {
return a[0];
}
Pero esta función también es O(1) :
int identity(int i) {
if(i == 0) {
sleep(60 * 60 * 24 * 365);
}
return i;
}
El tiempo de ejecución aquí está delimitado anteriormente por 1 año, pero la mayoría de las veces el tiempo de ejecución es del orden de nanosegundos.
Decir que el tiempo de ejecución es O(n) significa que hay una constante c tal que el tiempo de ejecución está limitado arriba por c * n , donde n mide el tamaño de la entrada. Por ejemplo, encontrar el número de ocurrencias de un entero particular en una matriz no ordenada de n enteros mediante el siguiente algoritmo es O(n) :
int count(int *a, int n, int item) {
int c = 0;
for(int i = 0; i < n; i++) {
if(a[i] == item) c++;
}
return c;
}
Esto se debe a que tenemos que iterar a través de la matriz inspeccionando cada elemento de a uno por vez.
De acuerdo con mi perspectiva,
O (1) significa que el tiempo para ejecutar una operación o instrucción a la vez es uno, en el análisis de complejidad de tiempo del algoritmo para el mejor de los casos.
Introducción a los algoritmos: segunda edición de Cormen, Leiserson, Rivest & Stein dice en la página 44 que
Como cualquier constante es un polinomio de grado 0, podemos expresar cualquier función constante como Theta (n ^ 0) o Theta (1). Sin embargo, esta última notación es un abuso menor, porque no está claro qué variable tiende a infinito. A menudo usaremos la notación Theta (1) para referirnos a una función constante o constante con respecto a alguna variable. ... Denotamos por O (g (n)) ... el conjunto de funciones f (n) tales que existen constantes positivas c y n0 tales que 0 <= f (n) <= c * g (n) para todo n> = n0. ... Tenga en cuenta que f (n) = Theta (g (n)) implica f (n) = O (g (n)), ya que la notación Theta es más fuerte que la notación O.
Si un algoritmo se ejecuta en O (1) tiempo, significa que asintóticamente no depende de ninguna variable, lo que significa que existe al menos una constante positiva que cuando se multiplica por uno es mayor que la complejidad asintótica (~ tiempo de ejecución) de la función para valores de n por encima de cierta cantidad. Técnicamente, es O (n ^ 0) tiempo.
La "notación de Big O" es una forma de expresar la velocidad de los algoritmos. n es la cantidad de datos con los que está trabajando el algoritmo. O(1) significa que, sin importar la cantidad de datos, se ejecutará en tiempo constante. O(n) significa que es proporcional a la cantidad de datos.
La forma más fácil de diferenciar O (1) y O (n) es comparar array y list.
Para la matriz, si tiene el valor de índice correcto, puede acceder a los datos de forma instantánea. (Si no conoce el índice y tiene que recorrer el conjunto, ya no será O (1))
Para la lista, siempre necesita recorrerla ya sea que conozca el índice o no.
O (1) no significa necesariamente "rápidamente". Significa que el tiempo que toma es constante y no se basa en el tamaño de la entrada a la función. La constante puede ser rápida o lenta. O (n) significa que el tiempo que toma la función cambiará en proporción directa al tamaño de la entrada a la función, denotada por n. Nuevamente, podría ser rápido o lento, pero se volverá más lento a medida que aumente el tamaño de n.
O (1) significa acceso aleatorio. En cualquier memoria de acceso aleatorio, el tiempo necesario para acceder a cualquier elemento en cualquier ubicación es el mismo. Aquí el tiempo puede ser cualquier número entero, pero lo único que hay que recordar es el tiempo que se tarda en recuperar el elemento en (n-1) la enésima ubicación será la misma (es decir, constante).
Mientras que O (n) depende del tamaño de n.
O (1) significa que el tiempo para acceder a algo es independiente del número de elementos en la colección.
O (N) significa que el tiempo para acceder a un elemento es proporcional al número (N) de elementos en la colección.
Se llama http://en.wikipedia.org/wiki/Big_O_notation y describe el tiempo de búsqueda de varios algoritmos.
O (1) significa que el peor tiempo de ejecución es constante. Para la mayoría de las situaciones, significa que no necesitas buscar en la colección, puedes encontrar lo que estás buscando de inmediato.
Significa que el acceso toma tiempo constante, es decir, no depende del tamaño del conjunto de datos. O (n) significa que el acceso dependerá linealmente del tamaño del conjunto de datos.
El O también se conoce como big-O.
Significa que el tiempo de acceso es constante. Ya sea que acceda desde 100 o 100.000 registros, el tiempo de recuperación será el mismo.
Por el contrario, el tiempo de acceso de O (n) indicaría que el tiempo de recuperación es directamente proporcional al número de registros desde los que está accediendo.
Tendrá que leer sobre el orden de la complejidad.
http://en.wikipedia.org/wiki/Big_O_notation
En resumen, O (1) significa que lleva un tiempo constante, como 14 nanosegundos, o tres minutos sin importar la cantidad de datos en el conjunto.
O (n) significa que lleva una cantidad de tiempo lineal con el tamaño del conjunto, por lo que un conjunto de dos veces tomará el doble de tiempo. Probablemente no quieras poner un millón de objetos en uno de estos.
O(1) siempre se ejecuta al mismo tiempo independientemente del conjunto de datos n. Un ejemplo de O (1) sería un ArrayList accediendo a su elemento con índice.
O(n) también conocido como Orden lineal, el rendimiento crecerá linealmente y en proporción directa al tamaño de los datos de entrada. Un ejemplo de O (n) sería una inserción y eliminación de ArrayList en posición aleatoria. Como cada inserción / eliminación subsiguiente en una posición aleatoria causará que los elementos en ArrayList se muevan a la izquierda de su matriz interna para mantener su estructura lineal, sin mencionar la creación de nuevas matrices y la copia de elementos del antiguo a una nueva matriz que toma tiempo de procesamiento caro, detrimento del rendimiento.