N elementos se almacenan en una lista ordenada doblemente enlazada. Para una operación de eliminación, se proporciona un puntero al registro que se eliminará. Para una operación de tecla de disminución, se proporciona un puntero al registro en el que se va a realizar la operación. Un algoritmo realiza las siguientes operaciones en la lista en este orden:
Θ(N) eliminar, O(log N) insertar, O(log N) buscar y Θ(N) disminuir tecla
¿Cuál es la complejidad temporal de todas estas operaciones juntas?
(A) O(Log 2 N)
(B) O(N)
(C) O(N 2 )
(D) Θ(N 2 Log N)
Respuesta: (C)
Explicación: La complejidad temporal de la operación de tecla de disminución es Θ(1) ya que tenemos el puntero al registro donde tenemos que realizar la operación. Sin embargo, debemos mantener ordenada la lista doblemente enlazada y, después de la operación de disminución de clave, debemos encontrar la nueva ubicación de la clave. Este paso tomará un tiempo Θ(N) y dado que hay operaciones de tecla decreciente Θ(N), la complejidad del tiempo se convierte en O(N²).
Tenga en cuenta que las otras tres operaciones tienen un límite inferior que éste.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA