usar sirve setdefaultcloseoperation que para exit_on_close ejemplo como closing close java algorithm big-o factorial asymptotic-complexity

java - ejemplo - setdefaultcloseoperation(jframe.exit_on_close) para que sirve



Ejemplo de O(n!)? (15)

@clocksmith Tienes toda la razón. Esto no está calculando n !. Tampoco es de O (n!). Lo ejecuté recogiendo los datos en la tabla de abajo. Por favor compare la columna 2 y la tres. (#nF es el # de llamadas a nFacRuntimeFunc)

n #nF n!

0 0 1 1 1 1 2 4 2 3 15 6 4 65 24 5 325 120 6 1956 720 7 13699 5040

Así que claramente si se realiza mucho peor que O (n!). A continuación se muestra un código de ejemplo para calcular n! recursivamente. Usted notará que es de orden O (n).

int Factorial(int n) { if (n == 1) return 1; else return n * Factorial(n-1); }

¿Qué es un ejemplo (en código) de una función O (n!)? Debe tomar un número apropiado de operaciones para ejecutarse en referencia a n; Es decir, estoy preguntando por la complejidad del tiempo.

Cía#

¿No sería esto O (N) en la complejidad del espacio? porque, la cadena en C # es inmutable.

string reverseString(string orgString) { string reversedString = String.Empty; for (int i = 0; i < orgString.Length; i++) { reversedString += orgString[i]; } return reversedString; }

Creo que llego un poco tarde, pero considero que snailsort es el mejor ejemplo de algoritmo determinista O (n!). Básicamente, encuentra la siguiente permutación de una matriz hasta que la ordena.

Se parece a esto:

template <class Iter> void snail_sort(Iter first, Iter last) { while (next_permutation(first, last)) {} }

Cualquier algoritmo que calcula toda la permutación de una matriz dada es O (N!).

El método recursivo que probablemente aprendió para tomar el determinante de una matriz (si tomó álgebra lineal) toma tiempo O (n!). Aunque no tengo muchas ganas de codificar todo eso.

Encontrar el determinante con la expansión por menores.

Muy buena explicación here .

# include <cppad/cppad.hpp> # include <cppad/speed/det_by_minor.hpp> bool det_by_minor() { bool ok = true; // dimension of the matrix size_t n = 3; // construct the determinat object CppAD::det_by_minor<double> Det(n); double a[] = { 1., 2., 3., // a[0] a[1] a[2] 3., 2., 1., // a[3] a[4] a[5] 2., 1., 2. // a[6] a[7] a[8] }; CPPAD_TEST_VECTOR<double> A(9); size_t i; for(i = 0; i < 9; i++) A[i] = a[i]; // evaluate the determinant double det = Det(A); double check; check = a[0]*(a[4]*a[8] - a[5]*a[7]) - a[1]*(a[3]*a[8] - a[5]*a[6]) + a[2]*(a[3]*a[7] - a[4]*a[6]); ok = det == check; return ok; }

Código desde here . También encontrará los archivos .hpp necesarios here .

Hay problemas, que son NP-complete (verificables en tiempo polinomial no determinista). Lo que significa que si la entrada se escala, entonces su cálculo necesario para resolver el problema aumenta más que mucho.

Algunos NP-hard son: problema de ruta hamiltoniana ( img abierto ), problema de vendedor ambulante ( img abierto )
Algunos NP-complete son: Problema de satisfacción booleana (Sat.) ( open img ), N-puzzle ( open img ), Knapsack problem ( open img ), Subgraph isomorphism problem ( open img ), Subset sum problem ( Open img ), Problema de clique ( img abierto ), Problema de cubierta de vértice ( img abierto ), Problema de conjunto independiente ( img abierto ), Problema de conjunto dominante ( img abierto ), Problema de coloreado de gráfico ( img abierto ),

Fuente: enlace 1 , NP-complete


Fuente: link

Tienes razón las llamadas recursivas deben tomar exactamente n! hora. Aquí hay un código como para probar el tiempo factorial para n valores diferentes. ¡El lazo interno corre para n! tiempo para diferentes valores de j, por lo que la complejidad del bucle interno es Big O (n!)

public static void NFactorialRuntime(int n) { Console.WriteLine(" N Fn N!"); for (int i = 1; i <= n; i++) // This loop is just to test n different values { int f = Fact(i); for (int j = 1; j <= f; j++) // This is Factorial times { ++x; } Console.WriteLine(" {0} {1} {2}", i, x, f); x = 0; } }

Aquí está el resultado de la prueba para n = 5, itera exactamente el tiempo factorial.

N Fn N! 1 1 1 2 2 2 3 6 6 4 24 24 5 120 120

Función exacta con complejidad de tiempo n!

// Big O(n!) public static void NFactorialRuntime(int n) { for (int j = 1; j <= Fact(i); j++) { ++x; } Console.WriteLine(" {0} {1} {2}", i, x, f); }

Un ejemplo clásico es el problema del vendedor ambulante a través de la búsqueda de fuerza bruta.

Si hay N ciudades, el método de la fuerza bruta intentará cada permutación de estas N ciudades para encontrar cuál es la más barata. Ahora el número de permutaciones con N ciudades es N! Haciendo que su complejidad sea factorial ( O(N!) ).

el ejemplo más simple :)

pseudocódigo

input N calculate N! and store the value in a vaiable NFac - this operation is o(N) loop from 1 to NFac and output the letter ''z'' - this is O(N!)

hay que ir :)

Como ejemplo real, ¿qué hay de generar todas las permutaciones de un conjunto de elementos?

Bogosort es el único "oficial" que he encontrado que se aventura en el área O (n!). Pero no es una O (n!) Garantizada ya que es de naturaleza aleatoria.

printf("Hello World");

Sí, esto es O (n!). Si crees que no lo es, te sugiero que leas la definición de BigOh.

Solo agregué esta respuesta debido al hábito molesto que tiene la gente de usar siempre BigOh, independientemente de lo que realmente significan.

Por ejemplo, estoy bastante seguro de que la pregunta pretendía hacerle a Theta (n!), ¡Al menos cn! Pasos y no más que Cn! pasos para algunas constantes c, C> 0, pero optó por usar O (n!) en su lugar.

Otra instancia: Quicksort is O(n^2) in the worst case , mientras que técnicamente es correcto (¡incluso heapsort es O (n ^ 2) en el peor de los casos!), Lo que realmente significan es que Quicksort is Omega(n^2) in the worst case

Hay que ir Este es probablemente el ejemplo más trivial de una función que se ejecuta en tiempo O(n!) (Donde n es el argumento de la función):

void nFacRuntimeFunc(int n) { for(int i=0; i<n; i++) { nFacRuntimeFunc(n-1); } }