Requisiti: Devi definire un tipo di collezione di sola lettura, che non aggiungerà, eliminerà o modificherà la collezione, ma solo interrogherà la collezione. SperiamoPiù veloce è la query, meglio è。
Confronti comuni tra insiemi
Quando si descrive la complessità dell'algoritmo, o(1), o(n), o(logn), o(logn), o(nlogn) sono comunemente usati per esprimere la complessità temporale dell'algoritmo corrispondente, che è l'espressione della complessità spaziotemporale dell'algoritmo. Viene utilizzato non solo per rappresentare la complessità temporale, ma anche per rappresentare la complessità spaziale.
O è seguito da una funzione tra parentesi che indica la relazione tra il tempo/spazio consumato da un algoritmo e la quantità di dati generati. dove n rappresenta la quantità di dati in ingresso.
Ad esempio, se la complessità temporale è O(n), significa che la quantità di dati aumenta più volte e il consumo di tempo aumenta anche più volte. Ad esempio, algoritmi di attraversamento comuni. Un altro esempio è la complessità temporale O(n^2), che significa che quando il volume dati aumenta n volte, ci vuole tempo per aumentare n tempi quadrati, che è una complessità temporale superiore a quella lineare. Ad esempio, l'ordinamento delle bolle è un tipico algoritmo O(n^2), che deve essere scansionato n × n volte per ordinare n numeri.
Un altro esempio è O(logn), quando i dati aumentano n volte, ci vuole tempo per aumentare i logn (il log qui si basa su 2, ad esempio, quando i dati vengono aumentati di 256 volte, il tempo richiesto aumenta solo di 8 volte, che è inferiore a quello lineare. La ricerca binaria è l'algoritmo di O (logn), che elimina la metà delle possibilità ogni volta che viene trovata, e la ricerca in 256 dati deve essere trovata solo 8 volte per trovare il bersaglio.
O(nlogn) è lo stesso, cioè n moltiplicato per logn; quando i dati vengono aumentati di 256 volte, il consumo di tempo aumenta di 256 * 8 = 2048 volte. Questa complessità è superiore alla linearità sotto il quadrato. Merge and sort è la complessità temporale di O(nlogn).
O(1) è la complessità spaziotemporale più bassa, cioè il tempo/spazio consumato è indipendente dalla dimensione dei dati di input; indipendentemente da quante volte i dati di input vengano aumentati, il tempo/spazio consumato rimane invariato. L'algoritmo di hashing è una tipica complessità temporale O(1), che può trovare il bersaglio dopo un singolo calcolo (indipendentemente dai conflitti), indipendentemente dalla dimensione dei dati.
Questo articolo utilizza la coppia BenchmarkDotNetList、HashSet、SortedSet、DictionaryPer la richiesta di benchmarking, si riferisce a quanto segue:
Il codice è il seguente:
Risultato del test: Trovare una chiave su un Dizionario o un HashSet è molto più veloce che cercare in una Lista e in un SortedSet. La complessità temporale degli algoritmi Dizionario e HashSet è O(1), e per risparmiare memoria, il Valore del Dizionario non ci è utile, quindi ho comunque scelto lo storage HashSet.
|
Pubblicato su 07/03/2022 16:47:50
|
|
|
|
Pubblicato su 07/03/2022 23:09:48
|
Padrone di casa|
Pubblicato su 09/03/2022 09:55:12
|
