Tempo di esecuzione insensibile all'input?

2

Ho letto quanto segue in Algorithms 4th Edition di Robert Sedgewick e Kevin Wayne :

Our first qualitative observation about most programs is that there is a problem size that characterizes the difficulty of the computational task. Normaly, the problem size is either the size of the input or the value of a command-line argument. Intuitively, the running time should increase with problem size, but the question is by how much it increases...

e

Another qualitative observation for many programs is that the running time is relatively insensitive to the input itself; it depends primarily on the problem size. If this relationship does not hold, we need to take steps to better understand and perhaps better control the runnig time's sensitivity to the input. But it does ofter hold, so we now focus on the goal of better quantifying the relationship between problem size and running time

La mia domanda è, se la dimensione di input (dimensione del problema del programma) aumenta, e quindi aumenta anche il tempo di esecuzione, perché il tempo di esecuzione del programma sarà relativamente insensibile all'ingresso? Sono confuso.

    
posta Anthony 15.08.2012 - 15:58
fonte

1 risposta

6

Penso che non stiano cercando di dire che il tempo di esecuzione non dipende dalla dimensione dell'input , ma piuttosto che è relativamente improbabile che cambi se si usano input diversi del stessa dimensione .

Ad esempio, un programma che immette n numeri diversi e calcola la somma di quei numeri ha probabilmente un tempo di esecuzione lineare, ma non dovrebbe importare molto se n i numeri sono tutti 0 o alcuni sono maggiori di 100 ecc.

    
risposta data 15.08.2012 - 16:17
fonte

Leggi altre domande sui tag