Tiempo de ejecucion

[jca1]

Buenas, tengo una consulta: dado un algoritmo que para diferentes valores de un mismo tamaño de de entrada (n) el tiempo de ejecucion varía; como puedo cacular la complejidad del algoritmo si para entradas de un mismo tamaño varia el tiempo de ejecucion. Digamos que para un determinado n el tiempo puede variar en el rango de dos funciones

[WHK]

Pueso eso va a depender del lenguaje de programación que estés usando, principalmente si el lenguaje utiliza memoria reservada de manera fija para almacenar contenido de bytes como c, pero en casos como Java, Python, etc no necesitarás calcular el tamaño asignado porque realmente no existe un tamaño como tal ya que cada variable se guarda en memoria de manera dinámica según el caso a excepción de los arrays primitivos.

En el caso de c++ debes reemplazar la entrada por std::string ya que este es de almacenamiento dinámico automático, en el caso de c debes contar la cantidad de bytes y modificar el tamaño asignado de la variable y reasignar el contenido copiandolo directamente desde la memoria, el problema es que esto da un gran problema y es que pierde integridad de datos de entrada ya que si tienes una variable de n espacios reservados, entonces no deberías permitir una entrada mayor a esa cantidad de bytes y copiar unicamente desde el primer byte hasta la posición de n con memcpy() y malloc(), intentar designar un espacio constante a una variable que modificará su tamaño con el tiempo es antinatural, en ese caso utiliza directamente una variable de espacio dinámico con un puntero en memoria.

Imagina que crear variables es algo así como crear columnas en una tabla de una base de datos, puedes asignar longitudes cortas o muy largas reservadas, pero esto puede impactar de manera negativa o positiva ya que si tienes pocos registros largos en columnas con longitud reservada muy alta tendrás mucho espacio inflado con bytes nulos y aumentarás el uso de memoria ram, y si tu columna es muy corta entonces puedes tener problemas de integridad de datos de entrada, por lo que asignar un valor certero para cada cosa es indispensable. Toma como ejemplo los RFC de estándares de protocolos, cada dato en general tiene su longitud máxima para no abusar de la memoria y poder reservar espacios estrictamente estáticos como por ejemplo la longitud máxima de una dirección url aceptada por el protocolo http, una cabecera, un nombre de dominio, un correo electrónico, una dirección ip, un mensaje, un id, etc.

Si el proyecto es tuyo, te recomiendo mantener las variables con longitud estática y ser estricto en sus controles para evitar su desbordamiento, eso aumentará drásticamente el performance en el uso de memoria y cpu o utilizar directamente std:: pero impactará directamente en el consumo de memoria y cpu y la velocidad de ejecución, lo mismo sucede con lenguajes interpretados y semicompilados que necesiten de una máquina virtual como java, c#, cpython, etc.

Digamos que para un determinado n el tiempo puede variar en el rango de dos funciones

En tu caso específico que neceistas que en x tiempo la longitud sea modificada deberás designar una variable numérica y actualizarla con pthread donde según ese valor numérico calculas cual tiene que ser la longitud deseada y modificas el tamaño de la entrada y de la variable que lo almacena, para lograr esto debes separar la funcionalidad del main() y pasarle como argumento a una función el valor máximo que soportará en memoria tus datos de entrada, con eso ya podrás hacerlo dinámico y cíclica. Sólo necesitarás unas 3 funciones nada más, el main, el hilo de proceso con el timer y la función que solicita el valor de entrada y listo. Si la aplicación no es persistente (solo se ejecuta una ves) entonces no necesitas el thread ni el timer, simplemente calculas el tiempo actual y en base a eso calculas la longitd dinámica de tu variable, luego copias de la memoria de argv y se lo pasas a la nueva variable teniendo cuidado del desbordamiento.

Mira esto:

https://en.wikipedia.org/wiki/Variable-length_array
https://www.geeksforgeeks.org/variable-length-arrays-in-c-and-c/

Saludos.

[jca1]

El problema en si es que quiero calcular la complejidad del algoritmo. Pero resulta por ejemplo para una entrada x de tamaño n tarda determinado tiempo. Luego para otra entrada m tambien de tamaño n tarda otro tiempo diferente. Es decir por ejemplo a partir de n no puedo definir la complejidad porque puede ser por ejemplo logaritmica hasta cuadratica. En el sentido de que el tiempo de ejecucion puede variar en ese rango por ejemplo y no podria estar definiendo una determinada complejidad.

[Serapis]

Debes considerar el tiempo 'n', para la unidad de ejecución básica de lo que sea que haga tu algoritmo.

Puede ser que tu algoritmo recorra un bucle y en función de determinadas situaciones verifique cada elemento, o solo algunos, por ello, siempre se debe considerar el tiempo de ejecución para 1 solo elemento... y luego considerar el caso del tiempo O= n*x, siendo n el tiempo unitario y 'x' los elementos que al caso pueda considerar un bucle (lo cual es variable).

También sucede a menudo que un algoritmo, tiene derivaciones según los datos presentes, en tal caso se calcula un valor medio, como el aceptado (o el valor mas frecuente). Si existe la posibilidad de considerar mejor y peor casos y se conoce su frecuencia pueden calcularse con más exactitud, si no un valor medio aceptable.

Por ejemplo, por mucho que se quiera un algoritmo de ordenación como 'Quicksort', no puede ofrecer un tiempo exacto para todos los casos dado un tamaño fijo del array a ordenar. Ya que dependerá del estado actual del array la cantidad de intercambios, comparaciones y particiones que se harán. ...existe un mejor y peor caso... hay dos modos de proceder:
- Considerar valores aleatorios para el array, ejecutar cierto número de veces y obtener el valor medio (deberán ser arrays muy grandes para que las interrupciones del S.O. no falsifiquen el tiempo aproximado, esto es que que la mayor parte dle tiempo sea proceso del algoritmo).
- Descomponer el algoritmo en sus unidades más elementales y considerar el tiempo para cada una de ellas... por ejemplo con quicksort habría que analizar el tiempo de intercambio entre valores del array y el tiempo de recorridos haciendo comparaciones satisfactorias.... puede exponerse finalmente el tiempo de una forma  funcional de modo que exija ser calculado para cada caso.

...Básicamente esto último, es lo que tendrás que hacer con distintos tamaños de arrays, ya que el tiempo unitario crece exponencialmente a medida que el array crece (en potencias de 2, dado el cariz del algoritmo).

p.d.: Nunca viene mal si el algoritmo presenta mejores y peores casos exponer el tiempo en tales situaciones, y explicar las condiciones en las que se dan tales casos.

[WHK]

Haz un benchmark desde una función interna y calcula el promedio de tiempo por x cantidad de datos entre a y b longitud y luego traspasa ese valor a tu código para determinar cuanto tiempo tardará ej procesar un conjunto de datos dependiendo de la longitud promedio. Pero creo que este proceso tardará más que el mismo intercambio de tamaño de memoria asignada para las variables xD

[jca1]

Nebire tu respuesta me aclaro mucho. Igual estaba expresando mal la pregunta disculpen. Siendo n la cantidad de elementos de entrada de mi algoritmo para una misma cantidad n mi algoritmo tarda diferentes tiempos para diferentes entradas de la misma cantidad. Por ejemplo ingreso 50 numeros una vez y luego ejecuto el algoritmo con otros 50 numeros y tardan diferentes tiempos. Seria en un rango entre tiempo log y cuadratico por ejemplo.

Segun entiendo y me aclararon deberia proponer los casos mas representativos para calcular la complejidad?

[Serapis]

Segun entiendo y me aclararon deberia proponer los casos mas representativos para calcular la complejidad?

Exacto, los más representativos. A veces también es preciso explicar mejor y peor caso si se dan.

Por ejemplo buscar el valor mayor de un array (que no está ordenado):
Ea una búsqueda lineal, exige recorrer todos en el array para garantizar que en efecto, 'detrás' no hay otro mayor, el tiempo por tanto sería el tiempo de comparación con 1 elemento, multiplicado por el número de elementos del array. En este ejemplo, no hay mejor ni peor casos, todos son iguales indistintamente de que el mayor se encontrare el primero, el último o en medio, esté repetido 1 o 50 veces.

Si en vez de buscar el mayor, buscamos un número dado pero el array está ordenado. El resultado nunca será exacto, pero puede saberse el mejor y peor casos: el mejor caso es que se encuentre a la primera y en el peor log(n) (en base 2), pués supònemos una búsqueda dicotómica (binaria). Pero no puede darse un valor exacto, siempre dependerá del valor buscado y el resto de valores en el array.

Todavía si la búsqueda es sobre una tabla hash, en vez de un array, la búsqueda es unitaria siempre, aunque el tiempo de la búsqueda nunca será igual, se considera que sí, porque la diferencia de tiempos entre uno u otro caso es mínimo. Ahora bien,, si lo que se quiere es explicar el algoritmo, entonces habría que resolverlo en la forma:
O = (Hash(v)) + Search(hash(v))
es decir el tiempo de hashear el valor, + el tiempo de buscarlo.
Incluso el tiempo de búsqueda puede variar si hubiera colisiones, luego con más exactitud sería la suma de 'Search(Hash(v))' para cada colisión hasta que se encuentre o no haya más colisiones (no existe).

Si no se reclama el detalle del algoritmo, se considera al caso, un tiempo unitario, pués calcular el hash del 'v' (valor), puede variar en función de los dígitos/caracteres que tenga, salvo que se trate como un número absoluto. Pero suele ser equivalente (sin apenas cambios) respecto del cálculo dle hahs de otro valor.
Todavía si se reclama, es preciso explicar los detalles (por ejemplo, del ejemplo), el caso de las colisiones, pués la frecuencia de los mismos se asume aumenta a medida que la ocupación de la T.Hash se fuere llenando.

En definitiva, debes considerar el objetivo destino de dicha información y darla más o menos detallada y precisa según se necesite o te requieran.