Compartilhamento de tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Prefácio

Se você quiser saber o que é complexidade de espaço/tempo, você precisa saber o que é uma estrutura de dados.

Isto pode ser entendido em dois níveis. Os dados existem em todas as partes de nossas vidas, como eventos internacionais que são tópicos importantes em Douyin, a remoção da armadura de Yongzheng, etc. O que nossos usuários podem ver são os dados que Douyin armazena no servidor back-end. Mas todos esses dados têm uma característica, ou seja, estão todos na lista de pesquisas importantes de Douyin, e essa lista é estruturada para garantir que os dados estejam em um local fixo para os usuários navegarem.

Além disso, com estruturas de dados, os algoritmos são inseparáveis. Bem, como acabamos de dizer, uma estrutura de dados armazena dados regularmente em uma estrutura, portanto, como acessar dados de forma eficiente da estrutura é um algoritmo.

complexidade de tempo

Com algoritmos, existe complexidade de tempo e complexidade de espaço. Como a memória dos computadores está ficando cada vez maior, a complexidade do tempo é mais importante do que a complexidade do espaço.Então, vamos primeiro entender a complexidade do tempo

conceito

Complexidade de tempo, a palavra mais importante é tempo, o tempo aqui se refere ao tempo em que um programa está sendo executado. Se a complexidade de tempo for menor, então o algoritmo provou ser melhor.O cálculo da complexidade do tempo é expresso pela fórmula funcional T(N)

Então, por que não calculamos antecipadamente a complexidade de tempo deste programa e escrevemos o código para a solução ideal? Isso envolve problemas de computador.

1. Como o tempo de execução do programa está relacionado ao ambiente de compilação e à configuração da máquina em execução, por exemplo, um programa de algoritmo usa um compilador antigo
   Compilar com um novo compilador e compilar com um novo compilador têm tempos de execução diferentes na mesma máquina.
2. 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.
3. 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.

Vejamos um trecho de código:

// 请计算⼀下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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Se você observar este código com base no número de execuções de contagem, ele deverá ser:
T(N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

Neste momento, alguém disse, isso int count=0 não conta;

Aqui subestimamos demais o nosso computador. A CPU do nosso computador pode ser executada centenas de milhões de vezes por segundo. É claro que esse pequeno tempo pode ser ignorado. Portanto, a complexidade de tempo que calculamos não é precisa, é apenas uma estimativa aproximada. Neste momento, usamos um novo símbolo para representá-la.

Representação assintótica de Big O

Notação Big O: É um símbolo matemático usado para descrever o comportamento assintótico de uma função; é usado aqui para representar a complexidade de tempo estimada;

Então ainda conta como T(N) aqui? Em caso afirmativo, não precisamos de utilizar outro símbolo para representá-lo. Isso envolve as regras para contar 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 inferior são removidos, porque quando N continua a aumentar, o impacto dos termos de ordem inferior no resultado torna-se cada vez menor. Quando N se torna infinito, pode ser ignorado.
2. Se o termo de ordem mais alta existir e não for 1, remova o coeficiente constante deste termo, pois à medida que N continua a crescer, esse coeficiente terá cada vez menos influência no resultado. Quando N for infinito, ele poderá 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.

Então observe o acima T(N)=N^ 2 + 2 ∗ N + 10. A ordem mais alta aqui é N2, portanto, removendo outras ordens mais baixas, a complexidade é (ON^2)

Helicóptero de pequena escala

// 计算Func3的时间复杂度？
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Aqui T(N)=M+N, então vamos calcular O(N) novamente, M e N aqui são ambos da mesma ordem, portanto não cumprem a primeira regra e não correspondem à segunda e terceira regras. , então o (N + M), então alguém perguntou: e se N for maior que M, deveria ser O (N). A questão aqui é: como você sabe que N é maior que M? E se M for maior que N, então ficaremos aqui apenas por segurança.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Aqui estamos procurando a posição do personagem em str. Aqui adicionarei um ponto de conhecimento:

• Nosso cálculo O é geralmente a complexidade do pior caso de um algoritmo.
  Aqui ele pode ser dividido em três níveis de complexidade:
  1. Melhor cenário
  Para encontrar o caractere na primeira posição da string, então:
  F (N) = 1, complexidade é o(1)

2. Situação média:
Para encontrar o caractere no meio da string, então:
F(N) = N/2,O(N/2)

3. Pior cenário
Para encontrar o caractere na última posição da string, então:
F(N) = N,O(N)

// 计算BubbleSort的时间复杂度？
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Na pior das hipóteses, como a ordem superior é mantida e n/2 é removido (o primeiro item) e o coeficiente (o segundo item) é ignorado, é ON^2

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

Quando n = 2, o número de execuções é 1
Quando n=4, o número de execuções é 2
Quando n=16, o número de execuções é 4
Supondo que o número de execuções seja x, então 2
x = n
Portanto o número de execuções: x = log n
Portanto: o pior caso de complexidade de tempo de func5 é:
O(log2 ^n)

Livros diferentes têm métodos de expressão diferentes. Os métodos de escrita acima não são muito diferentes.

complexidade do espaço

O que deve ser observado sobre a complexidade do espaço é que sua representação de cálculo também é representada por O, e suas regras seguem as mesmas três regras da complexidade do tempo.

Perceber

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.

Exemplo 1:

// 计算BubbleSort的时间复杂度？
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

O quadro da pilha de funções foi determinado durante a compilação.
Você só precisa prestar atenção ao espaço adicional solicitado pela função durante o tempo de execução.
Espaço adicional de aplicação para BubbleSort é
Há um número limitado de variáveis ​​locais, como exchange, que utiliza uma quantidade constante de espaço extra.
Portanto, a complexidade do espaço é O (1)