Estoy leyendo un libro llamado Principios de informática (2008), de Carl Reynolds y Paul Tymann (publicado por Schaum's Outlines).
El segundo capítulo presenta algoritmos con un ejemplo de búsqueda secuencial que simplemente itera a través de una lista de nombres y devuelve VERDADERO si se encuentra un nombre en la lista.
El autor continúa diciendo (página 17):
Decimos que el "orden de crecimiento" del algoritmo de búsqueda secuencial es n. La notación para esto es T (n). También decimos que un algoritmo cuyo orden de crecimiento está dentro de un factor constante de T (n) tiene un theta de NL, por ejemplo. "La búsqueda secuencial tiene una theta de n". El tamaño del problema es n, la longitud de la lista que se busca.
Encuentro esto realmente difícil de seguir. El libro está lleno de errores, por lo que no estoy seguro de si me falta algo o si hay un error tipográfico en el párrafo anterior. En inglés general, rara vez veo que una oración termine con "... digamos".
Estoy muy confundido.
¿Qué significa T? El libro no explica. ¿Es por tiempo o por Theta?
Si "una theta de NL" significa "La búsqueda secuencial tiene una theta de n". ¿Qué significa L? ¿'Lineal' o 'largo'?
He escrito a los editores pidiendo una explicación. Dijeron que enviarían mi mensaje a los autores. No han respondido. También he intentado buscar otras fuentes, pero todavía tengo la sensación de que estoy malinterpretando algo, así que no puedo descansar hasta que haya descifrado este párrafo.
Si alguien tiene una copia de ese libro, y ha entendido ese párrafo. Entonces, agradecería que me hiciera saber si ese párrafo es exacto o explicarlo en otras palabras. Gracias.
Respuestas:
El párrafo está mal. Desafortunadamente, se ve exactamente como el tipo de cosas que un estudiante que no entiende el material escribiría como respuesta a un ejercicio. Este tipo de tonterías no tiene cabida en un libro de texto. No hagas movimientos bruscos. Baja el libro. Aléjate del libro.
No. es la notación para una función llamada , que toma un argumento llamado . Esa función podría usarse para significar cualquier cosa. Existe una tradición de escribir relaciones de recurrencia para el tiempo de ejecución de los programas en la forma, por ejemplo, Pero no es un "orden de crecimiento", aquí: es una función específica definida a través de una relación de recurrencia. Y no puede simplemente escribir " " y esperar que las personas lean su mente y sepan que la función denota el tiempo de ejecución de algún algoritmo. aquí representa el tiempo.T(n) T n
Esto obviamente ha sido destrozado. Creo que los autores intentaron escribir algo como,
Pero, por favor, no decimos "tiene una theta de ", así como, si es tu notación de altura, no dirías "John tiene una de 180 cm". Simplemente no es una forma correcta de palabras. De hecho, decimos: "El tiempo de ejecución del algoritmo es theta (o theta of )". Tenga en cuenta, en particular, que es una herramienta para hablar de funciones matemáticas, no de algoritmos. Theta no significa que el tiempo de ejecución sea algo; más bien, es algo que puede usar para hablar sobre el tiempo de ejecución.n h h n n Θ
"NL", por cierto, denota el espacio de registro no determinista de la clase de complejidad , lo que no tiene ningún sentido en la posición que apareció en la cita original.
fuente
Parece que el autor está tratando de explicar la notación Big O , pero la renombró sin ninguna razón en particular y destrozó el texto por completo.T
Para una buena descripción de la notación Big O (así como de little-o y Theta), recomiendo el libro MIT Introducción a los algoritmos del profesor Leiserson.
Parece que una distinción importante es que refiere a la complejidad total de un algoritmo, que generalmente es tiempo , espacio o ambos. (por ejemplo, algunos algoritmos se ejecutan más lentamente con conjuntos de datos más grandes; algunos requieren más espacio de almacenamiento con datos más grandes; y algunos requieren más tiempo y más espacio) .O−notation
Parece que esta refiere solo a la medición del tiempo de un algoritmo y no tiene en cuenta los requisitos de almacenamiento.T−notation
fuente