minhas informações de contato
Correspondência[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Existem muitas maneiras e métodos no processo de resolução do mesmo problema de algoritmo. O resultado final é o mesmo e correto, mas a eficiência pode variar.
Assim como partir do mesmo lugar e chegar em outro, as formas de chegar ao local incluem aviões, trens, carros particulares... mas o tempo necessário é diferente e a economia também é diferente.
Depois que o algoritmo é escrito em um programa executável, ele requer recursos de tempo e recursos de espaço (memória) para ser executado. Portanto, a qualidade de um algoritmo é geralmente medida a partir de duas dimensões: tempo e espaço, nomeadamente complexidade de tempo e complexidade de espaço.
A complexidade do tempo mede principalmente a rapidez com que um algoritmo é executado, enquanto a complexidade do espaço mede principalmente o espaço extra necessário para executar um algoritmo.
Nos primeiros dias do desenvolvimento dos computadores, os computadores tinham uma capacidade de armazenamento muito pequena. Portanto, nos preocupamos muito com a complexidade do espaço. No entanto, após o rápido desenvolvimento da indústria informática, a capacidade de armazenamento dos computadores atingiu um nível muito elevado. Portanto, agora não precisamos mais prestar atenção especial à complexidade espacial de um algoritmo.
Quando eu jogo alguns jogos, meu telefone fica muito quente quando eu jogo, e alguns jogos não esquentam se eu os jogar, o que é inseparável da complexidade. Meu telefone está executando um algoritmo simples e funciona rapidamente, mas funciona. é complicado de executar. Algoritmo, para garantir que o tempo seja menos utilizado, a potência total deve estar habilitada, para que esquente.
Definição: Na ciência da computação, a complexidade de tempo de um algoritmo é uma fórmula funcional T(N), que descreve quantitativamente o tempo de execução do algoritmo. A complexidade do tempo mede a eficiência do tempo de um programa, então por que não calcular o tempo de execução do programa?
- Como o tempo de execução do programa está relacionado à configuração do ambiente de compilação e da máquina em execução, por exemplo, se um programa de algoritmo for compilado com um compilador antigo ou compilado com um novo compilador, o tempo de execução será diferente na mesma máquina.
- O mesmo programa de algoritmo tem tempos de execução diferentes usando uma máquina antiga de baixa configuração e uma nova máquina de alta configuração.
- E o tempo só pode ser testado depois que o programa é escrito, não calculado e avaliado por meio de reflexão teórica antes de escrever o programa.
Portanto, ao julgar o grau de atribuição de tempo de um algoritmo, não é considerado o tempo de execução do algoritmo, apenas o número de instruções executadas.
Caso:
// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
Através da observação:
Número de operações básicas realizadas pela Func1:
T(N)=N2+ 2*N + 10
Na prática, quando calculamos a complexidade do tempo, não calculamos o número exato de execuções do programa. Calcular o número exato de execuções ainda é muito problemático (diferentes sentenças de código do programa terão diferentes números de instruções compiladas). isto), calcular o número exato de execuções é de pouca importância, porque queremos apenas comparar o nível de crescimento do programa de algoritmo no cálculo da complexidade de tempo, ou seja, a diferença em T(N) quando N continua a aumentar. vimos acima que constantes e termos de ordem inferior têm pouco impacto nos resultados quando N continua a crescer, então só precisamos calcular o número aproximado de execuções que o programa pode representar para aumentar a ordem de grandeza. geralmente usado Use a notação assintótica de Big O.
A complexidade do espaço também é uma expressão matemática, que é o espaço adicional alocado temporariamente devido às necessidades do algoritmo durante a operação de um algoritmo.
A complexidade do espaço não é quantos bytes de espaço o programa ocupa. Porque em circunstâncias normais, o tamanho de cada objeto não será muito diferente, então a complexidade do espaço é calculada pelo número de variáveis.
As regras de cálculo da complexidade espacial são basicamente semelhantes à complexidade prática, e a notação assintótica Big O também é usada.
Nota: O espaço de pilha necessário quando a função está em execução (armazenamento de parâmetros, variáveis locais, algumas informações de registro, etc.) foi determinado durante a compilação, portanto, a complexidade do espaço é determinada principalmente pelo espaço adicional explicitamente solicitado pela função durante o tempo de execução . Claro
O espaço não é uma consideração fundamental no desenvolvimento actual dos computadores, mas o desperdício excessivo deve ser evitado.
Notação Big O: É um símbolo matemático usado para descrever o comportamento assintótico das funções.
Regras para passar para a notação assintótica Big O:
- 1. Na fórmula funcional de complexidade de tempo T(N), apenas os termos de ordem mais alta são retidos e os termos de ordem mais baixa são removidos, porque quando N continua a aumentar,
O impacto dos termos de ordem inferior nos resultados é cada vez menor e, quando N é infinito, eles podem ser ignorados.- 2. Se o termo de ordem mais alta existir e não for 1, remova o coeficiente constante deste termo, porque à medida que N continua a aumentar, este coeficiente
O impacto nos resultados é cada vez menor e, quando N é infinito, pode ser ignorado.- 3. Se não houver itens relacionados a N em T(N), mas apenas itens constantes, substitua todas as constantes aditivas pela constante 1.
Pior caso: número máximo de execuções (limite superior) para qualquer tamanho de entrada
Caso médio: número esperado de execuções para qualquer tamanho de entrada
Melhor caso: número mínimo de execuções (limite inferior) para qualquer tamanho de entrada
Na prática, a representação assintótica do Big O geralmente concentra-se no limite superior do algoritmo, que é a pior situação operacional.
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++count;
}
}
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
complexidade de tempo:
Omita o código que é executado uma vez, como count=0, este código.
Mantenha o número de execuções de código que têm grande impacto no tempo de execução
O número de execuções do primeiro loop é uma execução de loop duplo de NNãoão
O segundo loop é uma camada de tempos de execução de loop 2Nãoão
O terceiro ciclo é 10 vezes
A soma do número de execuções é T(N)=N2+2*N+10
Big O representa a complexidade do tempo, descarte o pequeno impacto e aproveite o limite
SOBRE2)
Complexidade do espaço:
A função Func1 se aplica ao tamanho do espaço. Por exemplo, int count = 0, aplica-se ao tamanho do espaço do tipo int Int M=10, também se aplica ao espaço do tipo int.
Esses dois espaços também são usados no loop sem espaço de aplicação adicional.
O tamanho do espaço do aplicativo é constante
A complexidade espacial expressa em Big O é:
O(1)
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%dn", count);
}
complexidade de tempo:
O número de vezes que o código é executado é maior que o primeiro loop, que é N*2.
O segundo loop é executado 10 vezes
Use O grande para representar a complexidade do tempo. O maior impacto é 2*N. O termo do coeficiente anterior é omitido:
SOBRE)
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++
k)
{
++count;
}
printf("%dn", count);
}
complexidade de tempo
Existem duas incógnitas, e o maior impacto está nos dois loops
O primeiro loop é executado M vezes
O segundo loop é executado N vezes
Deve ser um número desconhecido, não tenho certeza de qual é o maior e qual é o menor, não vou omitir.
O(M+N)
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%dn", count);
}
complexidade de tempo:
O maior impacto aqui é um ciclo
O número de vezes que o loop é executado é 100
é uma constante fixa
O(1)
const char* strchr(const char* str, int character)
{
const char* p_begin = str;
while (*p_begin != character)
{
if(*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
A função realizada por esta função é encontrar o subscrito de um caractere em um array.
O número de execuções aqui é incerto
É possível encontrar F(N)=1 de uma só vez
É possível encontrar F(N)=N/2 no meio
Pode ser encontrado no final, ou NULL é retornado se não for encontrado, F(N)=N
Big O considera o pior cenário:
A complexidade do tempo é O(N)
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
Este número de execuções está relacionado ao tamanho de n, mas não faz um loop n vezes. Deve ser porque a variável do loop será multiplicada por 2 durante o loop, e o loop saltará rapidamente. o valor da variável de loop cnt alcançará 1024.
Supondo que o número de ciclos seja x, então 2x=n
x=logn
Portanto, a complexidade do tempo é: O(longn)
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if(exchange == 0)
break;
}
}
Esta função completa a classificação ascendente da bolha
Há um loop aqui. Este loop é um loop aninhado de dois níveis.
O número de loops é indefinido
O pior cenário é que o loop externo seja executado n vezes
Então o loop interno será executado (n-1)+(n-2)+(n-3)+……+2+1+0
é uma sequência aritmética e a soma é:
A complexidade do tempo é: O(N)
Complexidade do espaço:
Não há espaço de aplicação adicional e o espaço aplicado é constante.
O(1)
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
complexidade de tempo:
Recursado N vezes
Portanto, a complexidade do tempo é: O(N)
Complexidade do espaço:
Cada vez que você recorre, você precisa solicitar espaço.
Recursado N vezes e aplicado para N vezes do espaço.
A complexidade do espaço é: O(N)
Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.
Correspondência[email protected]