búsqueda secuencial

Question

Para la búsqueda secuencial, lo que es el número medio de comparaciones necesarias para encontrar un registro en un archivo?

Answer 1

búsqueda secuencial comienza desde el principio del archivo y comprueba cada elemento de una sola de -ona hasta que se encuentra el elemento deseado. Suponiendo que el registro que está buscando existe en el archivo exactamente una vez y podría estar en cualquier lugar en el archivo con la misma probabilidad, el número medio de comparaciones es igual a la mitad el número de registros en el archivo.

Sin embargo, si el registro no existe en el archivo, se tendrá que examinar cada registro individual en el archivo antes de descubrir esto.

Answer 2

Para obtener una lista con n elementos, el mejor caso es cuando el valor es igual al primer elemento de la lista, en cuyo caso sólo se necesita una comparación. El peor caso es cuando el valor no está en la lista (o se produce sólo una vez al final de la lista), en cuyo caso n comparaciones son necesarios.

Asintóticamente , por lo tanto, el costo del peor caso y el costo esperado de búsqueda lineal son ambos O (n)

Answer 3

Me gustaría añadir algunos puntos que las respuestas anteriores no señala:

• Por otro lado, debemos tener en cuenta si el archivo está disponible en un dispositivo o difusión a través de múltiples dispositivos. En caso de carneros T, entonces la complejidad será O(T*N/(1+log(T))).

• En general, la búsqueda secuencial toma O(N) time complexity.

• Cuando se combina con estructuras de datos tales como R-Tree, se puede dar un mejor tiempo de la complejidad del caso O(N/(log(log(N)))) en el caso de registros en un archivo.

• Depende de la estructura / formato del archivo de tal manera que si los campos de datos están disponibles en un mapa hash, búsqueda secuencial es un atraso.