Diciamo che ottengo N oggetti come input, e ho bisogno di riorganizzarli in una diversa struttura dati. Ciò significa che la complessità dello spazio del mio algoritmo sarà O(N) . Ma cosa succede se sostituisco gli oggetti con i puntatori agli oggetti? Avrò ancora puntatori N , ma sarà ancora O(N) di complessità spaziale nonostante il fatto che ci sarà chiaramente meno memoria?
Diventiamo filosofici per un minuto.
Il numero di oggetti è cambiato da N? No? Quindi è ancora O (N) perché hai iniziato con la premessa che N era il numero di oggetti di input ed era quello che è stato scelto per misurare.
Ora potresti iniziare con una premessa diversa per una determinata struttura di dati, ad esempio nel caso in cui le singole strutture di dati siano in realtà un'unità complessa stessa. A volte questo potrebbe avere senso.
Ora per gli esempi.
Per quanto riguarda la tua domanda originale, supponiamo di avere una lista di numeri interi da ordinare. Se affermi che la tua complessità spaziale è O (N), non importa se scegli un intero a 16 bit o un intero a 64 bit o un puntatore a 32 bit su un intero a 8 bit da una prospettiva "big-Oh" - è ancora O (N) perché stai misurando il numero di elementi da ordinare.
Ma ora supponiamo di voler aggiornare per supportare qualsiasi lunghezza del numero intero piuttosto che limitare il problema. Ora, tecnicamente la tua complessità spaziale è ancora O (N). Ma se inizi a gestire grandi numeri, la variazione delle dimensioni del numero dovrebbe eventualmente portare a variazioni nella dimensione della struttura dei dati sottostanti. Ciò significa che la misurazione rispetto a N potrebbe non avere più senso, e tu come programmatore intelligente decidi di scegliere qualcosa di diverso da misurare e analizzare. Forse ora vuoi iniziare a pensare invece alla complessità dello spazio rispetto alle cifre!
Leggi altre domande sui tag complexity big-o