sort sheet rapper for examples dummies complexity cheat big algorithm time-complexity big-o

algorithm - sheet - ¿Es mi función O(n!) O es O((n-1)!) Más precisa?



big o rapper (4)

Escribí un algoritmo de búsqueda de fuerza bruta para el problema del vendedor ambulante y lo probé para ver el tiempo que demoran varios números de "ciudades". En la siguiente gráfica, podemos ver que el tiempo es aproximadamente proporcional a (n-1)! donde n es el número de ''ciudades''. ¡No es directamente proporcional a n! (después de todo, (n-1)! = n! / n ).

Mi pregunta es, ¿sigue siendo correcto decir que el algoritmo se ejecuta en O(n!) , O es mejor para mí decir O((n-1)!) ? Nunca he visto esto último antes, pero parece más preciso. Parece que he entendido mal algo aquí.

[t = tiempo tomado, n = número de ciudades]

La respuesta de Sven Marnach es realmente buena, solo quiero elaborar un poco sobre esta parte:

o ¿es mejor para mí decir O ((n-1)!)?

Como han dicho otros, O(n) suele ser lo suficientemente bueno. Si desea obtener más información sobre el problema, puede intentar encontrar y probar:

  • Un límite inferior (generalmente denotado por Ω(n) )
  • Un límite superior apretado

Básicamente, un límite inferior dice que, bajo ciertas asimilaciones, no puede haber un algoritmo que resuelva el problema de manera asintóticamente más rápida. Un límite superior ajustado es un límite superior que coincide con un límite inferior, es decir, tendría que probar un límite inferior de Ω(f(n)) y un límite superior de O(f(n)) . Si puede probar un límite inferior y un límite superior ajustado, significa que su algoritmo es un algoritmo asintóticamente óptimo para el problema.

Para dar un ejemplo concreto para esto: Seguramente usted conoce algoritmos de clasificación como la ordenación por combinación o la ordenación rápida y su límite superior de O(n log n)) . Donald Knuth demostró (hace décadas) que los algoritmos de ordenación basados ​​en comparación para enteros requieren al menos n log n comparaciones n log n , es decir, operaciones Ω(n log n) . Dado que tenemos un límite superior coincidente, se dice que tanto el ordenamiento por combinación como el ordenamiento rápido son asintóticamente óptimos (aunque su rendimiento difiere mucho en la práctica).

Por definición, O (f (n)) es el conjunto de todas las funciones que están dominadas asintóticamente por f (n), es decir, el conjunto de todas las funciones g (n) para las cuales hay constantes C y n_0, de manera que

g(n) < C * f(n) for all n > n_0

De esta definición, se deduce que O (n!) Es en realidad un superconjunto de O ((n-1)!), Ya que la función f (n) = n! es un miembro del primer conjunto, pero no del segundo conjunto. Los dos conjuntos no son en realidad iguales.

Sin embargo, es correcto decir que su problema es O (n!), Ya que esto solo establece un límite superior. No sería correcto decir que su problema es ϴ (n!), Ya que esto denota el comportamiento asintótico exacto hasta factores constantes.

No hay una gran diferencia en la práctica y, como se señaló en otra respuesta, puede redefinir n para indicar el número de ciudades menos una.

Usted podría simplemente probar como:

O ((n-1)!) Significa que hay una constante c como:

pasos de algoritmo (o complejidad de tiempo) <c (n-1)! <cn! / n <cn! para cada n> 1.

Entonces, ya que su función de complejidad de algoritmo es válida: pasos de algoritmo (o complejidad de tiempo)

tu algoritmo también es O (n!).

Así que probamos que si la complejidad de tiempo de su algoritmo es O ((n-1)!) Entonces también es O (n!).