Perché la complessità del recupero di un valore da un array è O (1)?

La chiave per capire perché l'accesso agli array è O (1) è capire che hanno una lunghezza nota. In un linguaggio come C, possiamo garantirlo allocando un blocco sequenziale di memoria. Poiché è sequenziale in memoria, possiamo usare l'aritmetica del puntatore per l'indirizzamento diretto e quindi l'accesso diretto. Un oggetto array seguirebbe un principio simile con la sua organizzazione interna, anche se l'implementazione potrebbe essere più complessa. Poiché tutto ciò che stiamo facendo è qualche aggiunta, un'operazione che richiede O (1) tempo, abbiamo un'operazione che richiede più di O (1) tempo. Questa aggiunta è anche il motivo per cui almeno in C e C ++, tutti gli elementi in una matrice devono essere dello stesso tipo. Sono tutti obbligati a occupare lo stesso numero di byte affinché questa aritmetica del puntatore funzioni.

Contrastareciòinunelencocollegatosingolarmenteincuiabbiamouniniziodefinitodell'elencoequindiaggiungiamoaquell'elencoavendounpuntatoreounpuntodiriferimentodell'indirizzoalnodosuccessivonell'elenco.Ogninodocontienedueelementi,unpuntatorealnodosuccessivonell'elencoeunelementodati.Dalmomentochenonpuoitornareindietro,ognivoltachevuoiunelementodall'elenco,anchesesaiesattamentedovesitrova,deviattraversarel'interoelencofinoaquell'elemento.Quindi,finiamoconO(n/2)perl'accessoalcasomedioeO(n)perilcasopeggiore.Possiamoattenuarnealcunifacendounalistadoppiamentecollegataconunpuntatoredicodaeunpuntatoreditesta,masiamoancoralimitatiaunaformadiaccessosequenziale,piuttostochecasuale.Impostiamol'ultimopuntatoresunullperdireessenzialmentealcomputerlastessacosachestiamodicendoquandodiamoladimensionediunarray.

Perché l'indice n di una matrice punta all'elemento n + 1 ^th dell'array (usando l'indicizzazione basata su zero). Alcuni semplici calcoli matematici ti permettono di calcolare la posizione esatta dell'elemento desiderato in O(1) .

Ulterioriletture
Java Array

Risposta semplice:

Because you can calculate 453 + 6 in O(1) time too.

Consente di scrivere del codice e guardarlo più da vicino.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  int index = atoi(argv[1]);
  int a[10];
  for(int i = 0; i < 10; i++) { a[i] = 42 + i; }

  printf("foo!\n");
  int val = a[index];
  printf("%d\n",val);
  return 0;
}

Eseguendo questa operazione attraverso gcc -S possiamo ottenere l'assembly e guardarlo più da vicino.

Il motivo per cui foo è lì, è così che posso individuare rapidamente il punto tra i due printf s.

    leaq    L_.str(%rip), %rdi
    movb    $0, %al
    callq   _printf
    leaq    L_.str1(%rip), %rdi
    movslq  -28(%rbp), %rcx
    movl    -80(%rbp,%rcx,4), %edx
    movl    %edx, -88(%rbp)
    movl    -88(%rbp), %esi
    movl    %eax, -92(%rbp)         ## 4-byte Spill
    movb    $0, %al
    callq   _printf

_{Disclaimer: non sono un addetto alle assemblee - sono passati decenni da quando ho lavorato con MIPS, e non ho mai fatto altro che dare un'occhiata a Intel. Potrei avere sbagliato. Questo potrebbe essere diverso sul tuo sistema, perché in realtà non eseguivo gcc, ma piuttosto clang.}

Dopo che il primo printf è terminato, inizia caricando l'indirizzo del formato per str1 ( "%d\n ). Da un po 'sopra che non ho incluso, -28(%rbp) è il risultato della chiamata atoi . Ho questo per evitare che il sistema cerchi di ottimizzare tutto (perché lo farà ). E fa anche un altro giro di cose.

Tuttavia, non vi è alcun loop lì. È fatto in un numero costante di istruzioni indipendentemente dall'indice che stai cercando. Questa è la definizione di O (1).

Osserviamo una parte precedente, la popolazione dell'array.

        movl    $0, -84(%rbp)
LBB0_1:                                 ## =>This Inner Loop Header: Depth=1
        cmpl    $10, -84(%rbp)
        jge     LBB0_4
## BB#2:                                ##   in Loop: Header=BB0_1 Depth=1
        movl    -84(%rbp), %eax
        addl    $42, %eax
        movslq  -84(%rbp), %rcx
        movl    %eax, -80(%rbp,%rcx,4)
## BB#3:                                ##   in Loop: Header=BB0_1 Depth=1
        movl    -84(%rbp), %eax
        addl    $1, %eax
        movl    %eax, -84(%rbp)
        jmp     LBB0_1
LBB0_4:
        leaq    L_.str(%rip), %rdi
        movb    $0, %al
        callq   _printf

E senti che puoi vedere il ciclo che popola la matrice. C'è un confronto, un salto se maggiore di un etichetta, roba e il salto alla testa dopo l'incremento di 1.

Il numero di volte che verrà eseguito dipende dalla dimensione dell'array (in questo caso 10). C'è solo un ciclo che itera su tutti gli indici. Questo è O (N).

Ora, se questa fosse una lista collegata piuttosto che una matrice, dovresti percorrere l'elenco collegato per trovare l'elemento n ^th . Quindi passare all'elemento n ^th sarebbe anche O (N). Ci sono modi per rendere più veloce l'accesso a un particolare elemento di un elenco collegato utilizzando altre strutture di dati - ma non è ancora O (1).