Ho trovato informazioni sul modo migliore per aggiornare intervalli di valori di array usando l'array di differenze. Funziona ma non riesco a capire perché funzioni.
Qualcuno potrebbe spiegarlo per me?
Invece di un normale array di un gruppo di valori, un array di differenze ricava il valore successivo dalle voci precedenti. Invece di
TheArray[] = {4,6,2,10};
Avresti
DiffArray[] = {4,2,-4,8};
Aiuta a pensare a ogni valore positivo con un segno più in primo piano. 4 + 2 è 6. 6-4 è 2. 2 + 8 è 10. Stesso risultato, più matematica per arrivarci.
È "Best" nel caso in cui lo spostamento dell'intero array su e giù possa avvenire nel tempo O (1). Non importa quanto grande sia l'array, lo spostamento richiede solo una operazione. Ma non puoi semplicemente estrarre un valore dall'array senza aggiungere TUTTI i valori che lo precedono, il che comporterebbe un sovraccarico di elaborazione significativamente maggiore. È utile per alcuni casi di nicchia. ... Non riesco a pensare a nessuno in cima alla mia testa.
Leggi altre domande sui tag algorithms