Eficiencia de Big O para variables múltiples

Question

Estoy tratando de calificar la eficiencia de una función donde la entrada es una matriz de cadenas. El algoritmo siempre itera a través de cada elemento en esta matriz. Estas cadenas contenidas en esta matriz son de longitud variable. En este ciclo for inicial, se llama a una función de reemplazo de caracteres en cada cadena. Creo que la función de reemplazo en sí misma sería O (n) donde n es la longitud de la cadena.

Así que estoy confundido sobre cómo evaluar la eficiencia de la gran o aquí. Si n es el tamaño de la matriz, sé que al menos será O (n). Pero con longitudes de cadena variables, ¿cómo calificaría la eficiencia general con el reemplazo de cadena? ¿Diría que n es el tamaño de la matriz y usa otras variables para representar los diferentes tamaños de cada cadena?

Answer 1

Veo dos maneras de decir esto (entre muchas posibles).

El primero es para decir que es O(N) donde N es el número total de caracteres.

La otra que podría decir es O(N*M) donde N es el número de cadenas y M es el número promedio de caracteres por cadena. Tenga en cuenta que esto es en realidad lo mismo que mi respuesta anterior. Podría decir M = k/N, por lo que obtiene O(N*k/N) o O(k) donde k es el número total de caracteres en todas las cadenas.

Answer 2

Personalmente, expresaría la eficacia a través de tamaño de los datos de entrada (a diferencia de la longitud de la matriz). Entonces, si la entrada es t bytes, el tiempo de ejecución será O(t). Y t aquí también es una longitud común de todas las cadenas.