Big O effeciency per più variabili

Question

Sto provando a valutare l'efficienza di una funzione in cui l'input è un array di stringhe. L'algoritmo scorre sempre attraverso ogni elemento di questo array. Queste stringhe contenute in questo array sono di lunghezza variabile. In questo ciclo for iniziale, viene chiamata una funzione di sostituzione carattere su ogni stringa. Credo che la funzione di sostituzione da sola sarebbe O (n) dove n è la lunghezza della stringa.

Quindi sono confuso su come valutare la grande efficienza qui. Se n è la dimensione dell'array, so che sarà almeno O (n). Ma con lunghezze di stringa variabili, come valuteresti l'efficienza complessiva con la sostituzione della stringa? Diresti n è la dimensione dell'array e usi altre variabili per rappresentare le diverse dimensioni di ciascuna stringa?

Answer 1

Vedo due modi per dirlo (tra i molti possibili).

Il primo è dire che è O(N) dove N è il numero totale di caratteri.

L'altro che si potrebbe dire è dove N è il numero di stringhe e M è il numero medio di caratteri per stringa. Si noti che questo è in realtà la stessa della mia risposta sopra. Potresti dire M = k/N, quindi ottieni O(N*k/N) o O(k) dove k è il numero totale di caratteri in tutte le stringhe.

Answer 2

Personalmente, esprimerei l'efficienza tramite dimensione dei dati di input (in contrasto con la lunghezza della matrice). Quindi, se l'input è t byte, il tempo di esecuzione sarà O(t). E t qui è anche una lunghezza comune di tutte le stringhe.