complexity-theory - paradigma - video teoria de la complejidad
Ejemplo del mundo real de la complejidad exponencial del tiempo. (4)
¿Qué hay de encontrar un subconjunto de enteros dentro de un conjunto de tal manera que su suma sea un valor designado X?
Creo que esto tiene complejidad O (2 ^ (n / 2))
Estoy buscando un ejemplo intuitivo, en el mundo real, de un problema que requiera (en el peor de los casos) una complejidad de tiempo exponencial para resolver una charla que estoy dando.
Aquí hay ejemplos de otras complejidades de tiempo que he encontrado (muchas de ellas extraídas de esta pregunta de SO ):
- O (1): determinar si un número es impar o par
- O (registro N): busca una palabra en el diccionario (mediante la búsqueda binaria)
- O (N) - leyendo un libro
- O (N log N): ordenar un mazo de cartas (utilizando la ordenación de combinación)
- O (N ^ 2): verifica si tienes todo en tu lista de compras en tu carrito
- O (infinito) - lanzar una moneda hasta que caiga sobre las cabezas
¿Algunas ideas?
La solución de fuerza bruta del problema del vendedor ambulante es O (n!) Que es aproximadamente O (N ^ N)
La solución de un problema de fuerza bruta e ingenua n-reinas.
Tienes que colocar n reinas en un tablero * n sin que sean tomadas por otros.
while there are untried configs, go to next solution and test it
Suponiendo que cada reina está en una fila dada, hay n posibilidades para que la reina se coloque y n para las otras (n-1) otras reinas (porque las filas duplicadas no están marcadas).
Por lo tanto, tienes una complejidad O (n ^ n)
- O (10 ^ N): intentar romper una contraseña probando cada combinación posible (asumiendo una contraseña numérica de longitud N)
ps ¿por qué tu último ejemplo es de complejidad O (infinito)? es búsqueda lineal O (N) ... hay menos de 7 mil millones de personas en el mundo.