Requisitos: Você precisa definir um tipo de coleção somente leitura, que não adicionará, excluirá ou modificará a coleção, mas apenas a consultará. EsperamosQuanto mais rápida a consulta, melhor。
Comparações comuns de conjuntos
Ao descrever a complexidade do algoritmo, o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) são comumente usados para expressar a complexidade temporal do algoritmo correspondente, que é a expressão da complexidade espaço-temporal do algoritmo. Ele é usado não apenas para representar complexidade temporal, mas também para representar complexidade espacial.
O é seguido por uma função entre parênteses que indica a relação entre o tempo/espaço consumido por um algoritmo e a quantidade de dados cultivados. onde n representa a quantidade de dados de entrada.
Por exemplo, se a complexidade de tempo for O(n), isso significa que a quantidade de dados aumenta várias vezes, e o consumo de tempo também aumenta várias vezes. Por exemplo, algoritmos comuns de deslocamento. Outro exemplo é a complexidade temporal O(n^2), que significa que quando o volume de dados aumenta n vezes, leva tempo para aumentar n tempos quadrados, o que é uma complexidade temporal maior do que a linear. Por exemplo, a ordenação de bolhas é um algoritmo típico de O(n^2), que precisa ser escaneado n × n vezes para ordenar n números.
Outro exemplo é O(logn), quando os dados aumentam n vezes, leva tempo para aumentar os logn times (o logaritmo aqui é baseado em 2, por exemplo, quando os dados são aumentados 256 vezes, o tempo necessário só aumenta 8 vezes, o que é menor que o linear. A busca binária é o algoritmo de O (logn), que elimina metade das possibilidades toda vez que é encontrada, e a busca em 256 dados só precisa ser encontrada 8 vezes para encontrar o alvo.
O(nlogn) é o mesmo, ou seja, n multiplicado por logn; quando os dados aumentam 256 vezes, o consumo de tempo aumenta 256 * 8 = 2048 vezes. Essa complexidade é maior que a linearidade abaixo do quadrado. Merge and sort é a complexidade temporal de O(nlogn).
O(1) é a menor complexidade espaço-temporal, ou seja, o tempo/espaço consumido é independente do tamanho dos dados de entrada; não importa quantas vezes os dados de entrada sejam aumentados, o tempo/espaço consumido permanece inalterado. O algoritmo de hash é uma complexidade típica de tempo O(1), que pode encontrar o alvo após um único cálculo (independentemente dos conflitos), não importa o tamanho dos dados.
Este artigo utiliza o par BenchmarkDotNetList、HashSet、SortedSet、DictionaryConsulta para benchmarking, consulte o seguinte:
O código é o seguinte:
Resultado do teste: Encontrar uma chave em um Dicionário ou HashSet é muito mais rápido do que procurar em uma Lista e no SortedSet. A complexidade temporal dos algoritmos Dicionário e HashSet é O(1), e para economizar memória, o Valor do Dicionário não nos serve de nada, então ainda escolhi armazenamento HashSet.
|
Publicado em 07/03/2022 16:47:50
|
|
|
|
Publicado em 07/03/2022 23:09:48
|
Senhorio|
Publicado em 09/03/2022 09:55:12
|
