Depende del tipo de acceso al que se refiera. Por ejemplo, “acceso aleatorio” podría simplemente significar que selecciona algún elemento aleatorio de un grupo de otros; en tal caso, incluso un O (1) es posible si se usa algo como una matriz directa.
Por lo general, “acceso” puede significar que está buscando algo específico. Es decir, debe coincidir con algunos criterios. En ese caso, la idea es tener los datos organizados de alguna forma para que no necesite buscar en todos ellos antes de encontrar lo que busca.
Las muestras donde dicho “acceso” (nota no necesariamente modificación) tienden a darle pasos de acceso promedio de O (log N) son cosas como la búsqueda binaria en una matriz ordenada, o el uso de un árbol de búsqueda binaria (especialmente una versión balanceada). De lo contrario (sin estructura), la búsqueda probablemente se convertiría en una operación O (N). Aunque hay formas de estructurarlo para que sea aún “mejor”, por ejemplo, el uso de una tabla hash podría darle acceso O (1).
- ¿Cuál es el lado teórico detrás de la informática?
- ¿Es la matemática un buen título para un programador?
- Cómo formular un programa entero donde todos estén representados en un horario
- Cómo aprender sobre qué pueden hacer las matemáticas en una computadora
- Suponiendo que uno tenga una experiencia limitada en programación, matemáticas y neurociencia, ¿cómo se ingresa a un programa de posgrado para inteligencia artificial o neurociencia computacional?
O (log N) tiende a significar que el algoritmo (y / o la estructura de datos) está usando un idioma de divide y vencerás. Es decir, en cada paso de la búsqueda, está dividiendo el número de posibilidades en el futuro en grupos más pequeños. Por ejemplo, en la búsqueda binaria, reduce a la mitad el número de elementos para buscar cada vez que marca un elemento. Es decir, en cada paso está dividiendo entre 2. Es decir, es el reverso de la cuadratura, por lo tanto, inicie sesión. Para ser más específico log-base-2, y N es la cantidad de elementos para buscar en su totalidad.