L'aggiunta di un vertice in un grafico rappresentato utilizzando una matrice di adiacenza richiede O (| v | ^ 2) complessità temporale in base al link ( operazione grafica > matrice di adiacenza > aggiungi vertice).
Ma non sono riuscito a trovare una ragione per cui? Dal momento che tutto ciò di cui abbiamo bisogno è aggiungere una riga e una colonna, che ovviamente prende O (| v |), qual è il ragionamento dietro questo?
Le matrici sono in genere archiviate in memoria contigua e il contenuto deve avere una mappatura definita dal layout di memoria sequenziale alla cella di matrice (x,y) (una mappatura tipica è descritta in questo ex post" Programmatori "). Ora, se c'è da aggiungere un nuovo vertice, si deve aumentare la memoria per una matrice |V|² a (|V|+1)² . Ciò significa che dovrai copiare l'intero contenuto della precedente matrice più piccola nella memoria appena allocata per la matrice più grande, perché la mappatura non si adatta più. Ovviamente è un'operazione O(|V|²) .
Si può mitigare questo problema fornendo una migliore strategia di allocazione della memoria, ad esempio, non aumentando la dimensione della matrice uno per uno, ma in fasi più grandi.
Leggi altre domande sui tag algorithms complexity math big-o graph