Ho creato una struttura dati con funzioni di inserimento, ricerca ed eliminazione basate sul numero di caratteri nella chiave.
Ad esempio se si tratta di una chiave basata su numero (base 10 ), la complessità per le funzioni date è nel peggiore dei casi uguale al numero di cifre nella chiave. Se fosse il caso, come potrei esprimerlo?
Ho fatto un po 'di lettura e mi sono inventato questo. O (log 10 ⟨N⟩) È giusto?
Normalmente, se il vincolo che ci interessa è la lunghezza del numero in bit piuttosto che il valore del numero o la dimensione / lunghezza di alcune strutture dati, semplicemente definiamo N come la lunghezza di il numero ed esprimi il big-O in termini di ciò. Quindi direi che le tue operazioni sono O (n) o tempo lineare e assicurati di menzionare da qualche parte che n è la lunghezza della chiave rispetto al valore della chiave o il numero di nodi già inseriti o qualsiasi altra cosa.
Questo è il più delle volte fatto nel contesto della fattorizzazione di interi. Ogni volta che qualcuno ti dice che dobbiamo ancora trovare un algoritmo tempo-polinomiale per trovare la fattorizzazione primaria di un intero, stanno parlando della complessità temporale dove N è definita come la lunghezza del numero intero. Se invece definisci N come valore dell'intero, l'ovvio algoritmo di forza bruta che prova semplicemente tutti i possibili fattori è ovviamente una soluzione temporale polinomiale. Questo è talvolta chiamato tempo pseudo-polinomiale . Quindi suppongo che potresti dire che le tue operazioni sono eseguite in "tempo pseudo-logaritmico" se lo vuoi davvero.
Se ti stai chiedendo perché facciamo questo, i motivi principali di cui sono a conoscenza sono che 1) La convenzione per big-O è che n indica sempre "la lunghezza / dimensione del input ", sia che l'input sia un albero con 50 nodi o un numero intero di 50 cifre. Quindi non è così arbitrario come potrebbe sembrare. 2) In pratica la lunghezza / dimensione dell'input sembra essere il fattore limitante. Il fatto di conoscere un algoritmo del tempo pseudo-polinomiale per la fattorizzazione primaria non cambia il fatto che non potrò mai forzare una chiave privata RSA con il mio laptop.
Leggi altre domande sui tag big-o