Requisitos: Necesitas definir un tipo de colección de solo lectura, que no añadirá, eliminará ni modificará la colección, sino que solo la consultará. EsperamosCuanto más rápida sea la consulta, mejor。
Comparaciones de conjuntos comunes
Al describir la complejidad del algoritmo, o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) se usan comúnmente para expresar la complejidad temporal del algoritmo correspondiente, que es la expresión de la complejidad espaciotemporal del algoritmo. Se utiliza no solo para representar la complejidad temporal, sino también para representar la complejidad espacial.
O va seguida de una función entre paréntesis que indica la relación entre el tiempo/espacio consumido por un algoritmo y la cantidad de datos cultivados. donde n representa la cantidad de datos de entrada.
Por ejemplo, si la complejidad temporal es O(n), significa que la cantidad de datos aumenta varias veces y el consumo de tiempo también aumenta varias veces. Por ejemplo, algoritmos comunes de desplazamiento. Otro ejemplo es la complejidad temporal O(n^2), lo que significa que cuando el volumen de datos aumenta n veces, tarda tiempo en aumentar n veces cuadradas, lo que es una complejidad temporal mayor que la lineal. Por ejemplo, la ordenación de burbujas es un algoritmo típico de O(n^2), que necesita ser escaneado n × n veces para ordenar n números.
Otro ejemplo es O(logn), cuando los datos aumentan n veces, tarda tiempo en aumentar las logn (el logaritmo aquí se basa en 2, por ejemplo, cuando los datos se incrementan 256 veces, el tiempo requerido solo aumenta 8 veces, lo que es menor que el lineal). La búsqueda binaria es el algoritmo de O (logn), que elimina la mitad de las posibilidades cada vez que se encuentra, y la búsqueda en 256 datos solo necesita encontrarse 8 veces para encontrar el objetivo.
O(nlogn) es el mismo, es decir, n multiplicado por logn; cuando los datos se multiplican por 256, el consumo de tiempo aumenta 256 * 8 = 2048 veces. Esta complejidad es mayor que la linealidad por debajo del cuadrado. Merge and sort es la complejidad temporal de O(nlogn).
O(1) es la menor complejidad espaciotemporal, es decir, el tiempo/espacio consumido es independiente del tamaño de los datos de entrada; no importa cuántas veces se aumenten los datos de entrada, el tiempo/espacio consumido permanece sin cambios. El algoritmo de hashing es una típica complejidad temporal O(1), que puede encontrar el objetivo tras un solo cálculo (independientemente de los conflictos), sin importar lo grandes que sean los datos.
Este artículo utiliza el par BenchmarkDotNetList、HashSet、SortedSet、DictionaryPara consultar para benchmarking, consulte lo siguiente:
El código es el siguiente:
Resultado de la prueba: Encontrar una clave en un Diccionario o HashSet es mucho más rápido que buscar en una Lista y en SortedSet. La complejidad temporal de los algoritmos Dictionary y HashSet es O(1), y para ahorrar memoria, el valor del Diccionario no nos sirve, así que aún elegí almacenamiento HashSet.
|
Publicado en 7/3/2022 16:47:50
|
|
|
|
Publicado en 7/3/2022 23:09:48
|
Propietario|
Publicado en 9/3/2022 9:55:12
|
