¿Cuál es el peor caso, el caso promedio y la mejor complejidad de tiempo de un algoritmo?

  • Mejor caso = tiempo más rápido para completar, con las entradas óptimas elegidas.
    Por ejemplo, el mejor caso para un algoritmo de ordenamiento serían datos que ya están ordenados.
  • Peor caso = tiempo más lento para completar, con entradas pesimales elegidas.
    Por ejemplo, el peor de los casos para un algoritmo de clasificación podría ser datos ordenados en orden inverso (pero depende del algoritmo particular).
  • Caso promedio = media aritmética. Ejecute el algoritmo muchas veces, utilizando muchas entradas diferentes de tamaño n que provienen de alguna distribución que genera estas entradas (en el caso más simple, todas las entradas posibles son igualmente probables), calcule el tiempo total de ejecución (agregando los tiempos individuales), y dividir por el número de pruebas. También es posible que deba normalizar los resultados según el tamaño de los conjuntos de entrada.

Related Content

Programadores: ¿A menudo considera el promedio, el peor y el mejor caso en mente al escribir un algoritmo?

¿Es útil el algoritmo de aprendizaje profundo en finanzas?

¿Cuáles son las ventajas de los algoritmos SVM?

¿Cómo se realiza la agrupación en el sondeo lineal en hashing con direccionamiento abierto?

¿Cuál es un buen algoritmo para priorizar mensajes DENTRO de su bandeja de entrada?

More Interesting

¿Cuál es la diferencia entre el algoritmo de Prim y el vecino más cercano?

¿Necesito tener el conocimiento de las estructuras de datos y el algoritmo, antes de comenzar a practicar en spoj, codchef, topcoder, etc.? Sé un poco de C ++.

¿Qué algoritmos y estructuras de datos se utilizan más en problemas del mundo real y software de producción?

Al explorar un museo, ¿es mejor usar BFS o DFS?

¿Existe algún algoritmo que realice el reconocimiento de entidades con nombre insensible a mayúsculas y minúsculas de oraciones cortas?

¿Cómo debo usar el libro Introducción a los algoritmos de Cormen de manera efectiva? ¿Es mejor elegir un tema que haya encontrado en algún lugar de la programación competitiva y leer un algoritmo relacionado con eso o revisarlo de principio a fin?

En el algoritmo EM, ¿debería aumentar el valor de la función objetivo a través de cada M-STEP?

¿Cuáles son algunos algoritmos interesantes que no tienen implementación conocida hasta la fecha?

¿Deben las clases de algoritmos incluir tareas de programación?

¿Cómo puede funcionar un algoritmo con un conjunto de datos pequeño pero da valores incorrectos en un conjunto de datos más grande?

¿Cuál es la mejor estructura de datos para un solucionador de ahorcado?

¿Cuál es la estrategia de divide y vencerás? Escribe un algoritmo para encontrar x a la enésima potencia usando el método de dividir y conquistar.

Juez en línea de Esfera (SPOJ): ¿Por qué el siguiente código da como resultado TLE? Quiero saber cómo se puede optimizar mi código para evitarlo.

¿Por qué la complejidad temporal del siguiente código O (logn)?

¿Por qué Java utiliza una implementación mediocre de hashCode para cadenas?