Cómo explicar la complejidad algorítmica a la abuela en términos simples

Has mencionado algunos ejemplos generales. Me gustaría decirle a la abuela qué es la complejidad y luego explicarle lo que significan algunas de las anotaciones grandes de Oh más utilizadas.

Le diría que la complejidad es el tiempo que le toma hacer algo en su cocina cuando su nieto pequeño le pide algo (la analogía aquí es que usted necesita realizar cierta tarea y la tarea toma un tiempo en completarse). Y mientras estamos en eso, digámosle que n es simplemente una cantidad de frascos que tiene en sus muchos estantes.

Ahora cavamos más profundo. Le diremos que O (1) es algo que puede hacer al mismo tiempo cada vez, independientemente de la cantidad de frascos que tenga. Como decir, guarda un nuevo frasco que el niño ha traído al estante más bajo. O obtener las galletas para niños del frasco con la etiqueta “galletas”, que ella sabe que están en un estante en particular en una posición particular. (Las analogías aquí se están insertando en una lista vinculada, por ejemplo, en el frente y en una búsqueda de tabla hash suponiendo que no hay colisión).

O (n) ahora, depende de cuántos frascos tiene la abuela. Digamos que el niño había escondido el reloj de la abuela en uno de los frascos. Ella tiene que mirar dentro de todos ellos una vez para encontrarlo. Si solo tiene 5 frascos, puede encontrarlo rápidamente. Si tiene 500, será una larga tarde. E incluso podría entender que, en el mejor de los casos, obtiene el reloj en el primer frasco y en el peor de los casos, tiene que revisar todos los frascos y fue en el último frasco que examinó. (búsqueda secuencial).

Supongo que dependiendo de si la abuela todavía está despierta, podemos seguir dando analogías como esta y educarla sobre el maravilloso tema de la teoría de la complejidad.

Lea este artículo de Knuth, “La complejidad de las canciones”. http://fivedots.coe.psu.ac.th/So …

Esto sugiere un enfoque para explicar la complejidad algorítmica sin introducir el concepto de instrucciones de máquina o problemas abstractos del tipo estudiado en cursos de informática.