No hay un resumen disponible de la notación O grande para operaciones en las estructuras de datos más comunes, incluidas matrices, listas vinculadas, tablas hash, etc.¿Cuál es la complejidad del tiempo de indexación, inserción y eliminación de estructuras de datos comunes?
Supongo que comenzaré con la complejidad de tiempo de una lista vinculada:
Indexing ----> o (n)
Inserción/Eliminación en el extremo ----> o (1) o o (n)
Inserción/Eliminación en medio ---> o (1) con el iterador O (n) sin
La complejidad del tiempo para la inserción en el dep final finaliza si tiene la ubicación del último nodo, si lo hace, sería O (1) de otra manera tendrá que buscar a través de la lista vinculada y la complejidad del tiempo saltará a O (n).
amortizado Big-S para tablas hash:
Nota que hay es un factor constante para el algoritmo hash, y la amortización significa que el rendimiento real medido puede variar drásticamente.
árboles¿Qué significa Big-O al insertar N elementos en el conjunto hash? Pensar dos veces. –
Amortizado, es N. Sin embargo, puede tener problemas para redimensionar la matriz de respaldo. Además, depende de su método para manejar conflictos. Si encadenas y tu algoritmo de inserción de encadenamiento es N (como en la cola de una lista con un solo enlace), puede convertirse en N^2. –
Esto está mal. Tiene la definición incorrecta de "amortizado". Amortizado significa el tiempo total para hacer un conjunto de operaciones dividido por el número de operaciones. El peor rendimiento del caso para insertar N elementos es definitivamente O (N^2), no O (N). Entonces las operaciones anteriores siguen siendo el O (n) peor caso, amortizado o no. Lo está confundiendo con la complejidad del tiempo "promedio" asumiendo una cierta distribución de funciones hash, que es O (1). – newacct
rojo-negro:
Tenga en Tenga en cuenta que a menos que esté escribiendo su propia estructura de datos (por ejemplo, la lista vinculada en C), puede depender drásticamente de la implementación de las estructuras de datos en su idioma/marco de referencia. Como ejemplo, eche un vistazo al benchmarks of Apple's CFArray over at Ridiculous Fish. En este caso, el tipo de datos, un CFArray del marco de CoreFoundation de Apple, en realidad cambia las estructuras de datos dependiendo de cuántos objetos hay realmente en la matriz, cambiando de tiempo lineal a tiempo constante en alrededor de 30,000 objetos.
Esto es realmente una de las cosas bellas acerca de la programación orientada a objetos - que no es necesario saber cómo funciona, solo que funciona, y el 'cómo funciona' puede cambiar dependiendo de los requerimientos .
información sobre este tema ya está disponible en la Wikipedia en: Search data structure
+----------------------+----------+------------+----------+--------------+
| | Insert | Delete | Search | Space Usage |
+----------------------+----------+------------+----------+--------------+
| Unsorted array | O(1) | O(1) | O(n) | O(n) |
| Value-indexed array | O(1) | O(1) | O(1) | O(n) |
| Sorted array | O(n) | O(n) | O(log n) | O(n) |
| Unsorted linked list | O(1)* | O(1)* | O(n) | O(n) |
| Sorted linked list | O(n)* | O(1)* | O(n) | O(n) |
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n)** | O(n) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) |
+----------------------+----------+------------+----------+--------------+
* The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time.
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.
Hay una cierta confusión en la eliminación en la matriz. Algunos dicen: toma O (n) tiempo para encontrar el elemento que desea eliminar. Luego, para eliminarlo, debe desplazar todos los elementos a la derecha un espacio a la izquierda. Esto también es O (n), por lo que la complejidad total es lineal. Y también dicen algunos, no es necesario llenar el espacio en blanco, se puede llenar con el último elemento. –
Además, ¿qué ocurre si queremos insertar un elemento en una matriz en una primera posición? ¿Eso no causaría que toda la matriz se moviera? Entonces, ¿no debería O (n) ser el tiempo de inserción de una matriz? –
Tenga en cuenta que debe * distinguir * entre una ** ordenada ** y una ** matriz ordenada **. Cambiar/llenar los elementos de la matriz es solo una preocupación de una matriz ordenada, por lo tanto, la complejidad lineal en lugar de 'O (1)' en una matriz no ordenada. Con respecto a sus ideas sobre cómo encontrar el elemento que desea eliminar, nuevamente debe distinguir entre ** encontrar ** un elemento y ** eliminar **. La complejidad del borrado supone que ya conoce el elemento que va a eliminar, por eso tiene 'O (n)' en una matriz ordenada (requiere desplazamiento) y 'O (1)' en una matriz no ordenada. – Mobiletainment
La complejidad de la inserción en el medio ** ** de una lista vinculada singularmente es O (n). Si la lista está doblemente enlazada y sabe que el nodo que desea insertar en ella es O (1) –
, olvidé agregar la parte del iterador. Gracias por señalarlo –
@Rob: puede ser una tonta duda, pero no soy capaz de entender cómo se puede insertar en la lista doblemente enlazada en O (1)? si tengo '1 4' y si tengo que insertar 5 entre 3 y 4, y todo lo que tengo es un puntero al nodo principal (es decir, 1) tengo que atravesar en O (n). ¿Me estoy perdiendo de algo? – Bhushan