La peor complejidad de tiempo para un algoritmo

StackOverflow https://stackoverflow.com/questions/331295

Pregunta

¿Cuál es la peor complejidad de tiempo del caso t (n): - Estoy leyendo este libro sobre algoritmos y como ejemplo. cómo obtener la T (n) para ... como la selección Ordenar Algoritmo

Me gusta si estoy tratando con el selectionSort (A [0..n-1]) 

//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order

déjame escribir un pseudocódigo 

for i <----0 to n-2 do
  min<--i
for j<--i+1 to n-1 do
   ifA[j]<A[min] min <--j
swap A[i] and A[min]

-------- También lo escribiré en C # --------------- 

private int[] a = new int[100];

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
  int i, j;
  int min, temp;

  for( i = 0; i < x-1; i++ )
  {
    min = i;

    for( j = i+1; j < x; j++ )
    {
      if( a[j] < a[min] )
      {
        min = j;
      }
    }

    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
  }
}

==================

Ahora cómo obtener la t (n) o como se conoce la peor complejidad de tiempo del caso

Otros consejos

Eso sería O (n ^ 2).

La razón es que tiene un solo ciclo for anidado en otro ciclo for. El tiempo de ejecución del bucle for interno, O (n), ocurre para cada iteración del bucle for externo, que nuevamente es O (n). La razón por la cual cada uno de estos individualmente es O (n) es porque toman una cantidad de tiempo lineal dado el tamaño de la entrada. Cuanto mayor sea la entrada, más tiempo tardará en una escala lineal, n.

Para resolver las matemáticas, que en este caso es trivial, simplemente multiplique la complejidad del bucle interno por la complejidad del bucle externo. n * n = n ^ 2. Porque recuerde, para cada n en el bucle externo, debe volver a hacer n para el interno. Para aclarar: n veces para cada n.

O (n * n).

O (n ^ 2)

Por cierto, no deberías mezclar la complejidad (denotada por big-O) y la función T. La función T es el número de pasos que debe seguir el algoritmo para una entrada determinada.

Entonces, el valor de T (n) es el número real de pasos, mientras que O (algo) denota una complejidad. Por el abuso convencional de notación, T (n) = O (f (n)) significa que la función T (n) tiene como máximo la misma complejidad que otra función f (n), que generalmente será la función más simple posible de su clase de complejidad.

Esto es útil porque nos permite centrarnos en el panorama general: ahora podemos comparar fácilmente dos algoritmos que pueden tener funciones T (n) de aspecto muy diferente al observar cómo funcionan " a largo plazo ejecutar " ;.

Otro flashback doctoral-comp aquí.

Primero, la función T es simplemente la cantidad de tiempo (generalmente en una cierta cantidad de pasos , sobre los cuales más abajo) toma un algoritmo para realizar una tarea. ¡Qué & Quot; paso & Quot; es decir, está algo definido por el uso; por ejemplo, es convencional contar el número de comparaciones en los algoritmos de clasificación, pero el número de elementos buscados en los algoritmos de búsqueda.

Cuando hablamos del peor momento de un algoritmo, generalmente lo expresamos con " notación big-O " ;. Por lo tanto, por ejemplo, escucha que la ordenación de burbujas lleva O (n & # 178;) tiempo. Cuando usamos la notación O grande, lo que realmente estamos diciendo es que el crecimiento de alguna función, en este caso T, no es más rápido que el crecimiento de alguna otra función por una constante. Eso es

T (n) = O (n & # 178;)

significa para cualquier n , no importa cuán grande sea, hay una constante k para la cual T (n) & # 8804; kn & # 178; . Un punto de cierta confusión aquí es que estamos usando & Quot; = & Quot; firmar de forma sobrecargada: no significa que los dos sean iguales en sentido numérico, solo que estamos diciendo que T (n) está delimitado por kn & # 178; .

En el ejemplo en su pregunta extendida, parece que están contando el número de comparaciones en el bucle for y en la prueba; Sería útil poder ver el contexto y la pregunta que están respondiendo. En cualquier caso, sin embargo, muestra por qué nos gusta la notación big-O: W (n) aquí está O (n) . (Prueba: existe una constante k, es decir, 5, para la cual W (n) & # 8804; k (3n) +2. Sigue por la definición de O (n ) .)

Si desea obtener más información al respecto, consulte cualquier texto de algoritmo bueno, por ejemplo, Introducción a los algoritmos , por Cormen et al.

escriba pseudocódigos para buscar, insertar y eliminar información del alumno de la tabla hash. calcular las complejidades de tiempo mejores y peores casos

3n + 2 es la respuesta correcta en lo que respecta al bucle. En cada paso del bucle, se realizan 3 operaciones atómicas. j ++ es en realidad dos operaciones, no una. y j     

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top