He visto este término "O (1) tiempo de acceso" que 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?¿Qué significa "O (1) access time"?
Ver también
Vas a querer leer sobre el orden de la complejidad.
http://en.wikipedia.org/wiki/Big_O_notation
En resumen, O (1) significa que se necesita un tiempo constante, al igual que 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 dos veces el tamaño tomará el doble de tiempo. Probablemente no quieras poner un millón de objetos en uno de estos.
Para ser pedante, no significa que el tiempo de ejecución (o el número de operaciones, etc.) sea constante. Significa que hay una constante tal que el tiempo de ejecución (o número de operaciones, etc.) está limitado por encima de la constante. Todavía podría haber una gran variación en el tiempo de ejecución: por ejemplo, 'int main() {int n; cin >> n; if (n == 0) {sleep (60 * 60 * 24 * 365); } cout << n; } 'es' O (1) '. – jason
En esencia, esto significa que se necesita la misma cantidad de tiempo para buscar un valor en su colección si tiene una pequeña cantidad de artículos 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 se deben recorrer 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.
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 O (n) indicaría que el tiempo de recuperación es directamente proporcional a la cantidad de registros a los que está accediendo.
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.
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.
Se llama Big O notation y describe el tiempo de búsqueda de varios algoritmos.
O (1) significa que el peor de los casos 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.
Reemplazar el "tiempo de búsqueda" con "el peor de los casos" tiempo "y estoy contigo. –
@Seb: Creo que fue un nombre inapropiado de su parte, específicamente porque OP preguntó sobre el tiempo de acceso. – jkeys
La "notación 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.
Básicamente, O (1) significa su tiempo de cálculo es constante, mientras que O (n) significa que dependerá linealmente del tamaño de entrada - es decir, en bucle a través de una matriz tiene O (n) - sólo bucle -, porque depende del número de elementos, mientras que calcular el máximo entre números ordinarios tiene O (1).
Wikipedia podría ayudar también: http://en.wikipedia.org/wiki/Computational_complexity_theory
La forma más sencilla para diferenciar O (1) y O (n) está comparando matriz y lista.
Para la matriz, si tiene el valor de índice correcto, puede acceder a los datos al instante. (Si no conoce el índice y tiene que recorrer el conjunto, ya no será O (1))
Para ver la lista, siempre debe recorrerla ya sea que conozca el índice o no.
Estaba buscando un ejemplo de O (1) y solo esta respuesta tiene la explicación para ello. – neelmeg
O (1) no significa necesariamente "rápidamente". Significa que el tiempo que toma es constante, y no en función del 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.
Introducción a los algoritmos: Segunda edición por Cormen, Leiserson, Rivest & Stein dice en la página 44 que
Dado que cualquier constante es un polinomio de grado-0 , podemos expresar cualquier función constante como Theta (n^0) o Theta (1). Esta última notación es un abuso menor de , sin embargo, porque es no está claro qué variable tiende a infinito. A menudo usaremos la notación Theta (0) para indicar una constante o una función constante con respecto de alguna variable. ... Nos denotado por O (g (n)) ... el conjunto de funciones f (n) de modo que existen constantes positivas c y n0 tales que = 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) vez, significa que asintóticamente no depende de cualquier variable, lo que significa que existe constante al menos un positivo que cuando se multiplica por uno es mayor que la complejidad asintótica (~ runtime) de la función para valores de n superiores a cierta cantidad. Técnicamente, es O (n^0) tiempo.
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).
Considerando que O (n) depende del tamaño de n.
No tiene nada que ver con el acceso aleatorio: consulte la [respuesta aceptada] (http://stackoverflow.com/a/697935/836214) publicada casi un año antes de esta respuesta para obtener más información – Krease
Cada respuesta que responde actualmente a esta pregunta le dice que el O(1) significa tiempo constante (lo que sea que ocurra 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 anteriormente por c, independientemente de la entrada. Por ejemplo, volviendo 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 es O(1) también:
int identity(int i) {
if(i == 0) {
sleep(60 * 60 * 24 * 365);
}
return i;
}
El tiempo de ejecución aquí está acotado superiormente por 1 año, pero la mayoría de el tiempo en que 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á acotado superiormente por c * n, donde n mide el tamaño de la entrada. Por ejemplo, encontrar el número de ocurrencias de un número entero particular, en una matriz sin clasificar de n números 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 es porque tenemos que iterar a través de la matriz de la inspección de cada elemento de una en una .
Según mi perspectiva,
O (1) significa tiempo para ejecutar una operación o instrucción a la vez es uno, en el análisis de complejidad de tiempo de algoritmo para mejor de los casos.
Intente más. Esa pregunta en particular necesita no solo una perspectiva sino una definición clara. – Alfabravo
¿Qué acabo de leer? Hombre común – shashwatZing
O(1) ejecute siempre 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 Pedido 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 e 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 hacia 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.
Esto podría ayudar: http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on/471206#471206 –