Compartir tecnología

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

Prefacio

Si quieres saber qué es la complejidad espacio/temporal, debes saber qué es una estructura de datos.

Esto se puede entender en dos niveles. Los datos existen en todas partes de nuestras vidas, como eventos internacionales que son temas candentes sobre Douyin, la eliminación de la armadura de Yongzheng, etc. Lo que nuestros usuarios pueden ver son los datos que Douyin almacena en el servidor backend. Pero todos estos datos tienen una característica, es decir, todos están en la lista de búsqueda activa de Douyin, y esta lista está estructurada para garantizar que los datos estén en una ubicación fija para que los usuarios puedan navegar.

Además, los algoritmos son inseparables de las estructuras de datos. Bueno, como acabamos de decir, una estructura de datos almacena datos regularmente en una estructura, por lo que cómo acceder a los datos de manera eficiente desde la estructura es un algoritmo.

complejidad del tiempo

Con los algoritmos, existe complejidad temporal y complejidad espacial. Debido a que la memoria de las computadoras es cada vez mayor, la complejidad del tiempo es más importante que la complejidad del espacio.Entonces, primero comprendamos la complejidad del tiempo.

concepto

Complejidad del tiempo, la palabra más importante es tiempo, el tiempo aquí se refiere al momento en que se ejecuta un programa. Si la complejidad del tiempo es menor, se demuestra que el algoritmo es mejor.El cálculo de la complejidad del tiempo se expresa mediante la fórmula funcional T(N)

Entonces, ¿por qué no calculamos de antemano la complejidad temporal de este programa y escribimos el código para la solución óptima? Se trata de problemas informáticos.

1. Debido a que el tiempo de ejecución del programa está relacionado con el entorno de compilación y la configuración de la máquina en ejecución, por ejemplo, un programa de algoritmo utiliza un compilador antiguo.
   Compilar con un compilador nuevo y compilar con un compilador nuevo tienen tiempos de ejecución diferentes en la misma máquina.
2. El mismo programa de algoritmo tiene diferentes tiempos de ejecución utilizando una máquina antigua de baja configuración y una máquina nueva de alta configuración.
3. Y el tiempo solo se puede probar después de escribir el programa, no calcularlo ni evaluarlo mediante el pensamiento teórico antes de escribir el programa.

Veamos un fragmento 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

Si observa este código según el número de ejecuciones de count, debería ser:
T(N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

En este momento, alguien dijo, ¿ese int count=0 no cuenta?

Aquí subestimamos demasiado nuestra computadora. La CPU de nuestra computadora puede ejecutarse cientos de millones de veces por segundo. Por supuesto, este pequeño tiempo puede ignorarse. Por lo tanto, la complejidad del tiempo que calculamos no es precisa, es solo una estimación aproximada. En este momento, usamos un nuevo símbolo para representarla.

Notación asintótica de Big O

Notación O grande: es un símbolo matemático que se usa para describir el comportamiento asintótico de una función; aquí se usa para representar la complejidad del tiempo estimada;

Entonces, ¿aquí todavía cuenta como T(N)? Si es así, no necesitamos usar otro símbolo para representarlo. Esto involucra las reglas para contar O:

1. En la fórmula funcional de complejidad temporal T (N), solo se retienen los términos de orden más alto y se eliminan los términos de orden más bajo, porque cuando N continúa aumentando, el impacto de los términos de orden más bajo en el resultado se vuelve cada vez menor. Cuando N es infinito, se puede ignorar.
2. Si el término de orden más alto existe y no es 1, elimine el coeficiente constante de este término, porque a medida que N continúa creciendo, este coeficiente tendrá cada vez menos influencia en el resultado. Cuando N es infinito, puede ignorarse.
3. Si no hay N elementos relacionados en T(N) sino solo elementos constantes, reemplace todas las constantes aditivas con la constante 1.

Luego mire lo anterior T(N)=N^ 2 + 2 ∗ N + 10. El orden más alto aquí es N2, por lo que eliminando otros órdenes bajos, la complejidad es (ON^2)

picadora a pequeña 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

Aquí T (N) = M + N, entonces calculemos O (N) nuevamente. M y N aquí son ambos del mismo orden, por lo que no cumplen con la primera regla y no corresponden a la segunda y tercera reglas. , entonces o (N + M), entonces alguien preguntó, ¿qué pasa si N es mayor que M? ¿Debería ser O (N)? La pregunta aquí es, ¿cómo se sabe que N es mayor que M? ¿Qué pasa si M es mayor que N, entonces nos quedamos aquí solo para estar seguros?

// 计算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

Aquí buscamos la posición del personaje en str. Aquí agregaré un punto de conocimiento:

• Nuestro cálculo de O es generalmente la complejidad del peor de los casos de un algoritmo.
  Aquí se puede dividir en tres niveles de complejidad:
  1. Mejor escenario
  Para encontrar el carácter en la primera posición de la cadena, entonces:
  F (N) = 1, la complejidad es o(1)

2. Situación media:
Para encontrar el carácter en el medio de la cadena, entonces:
F(N) = N/2,O(N/2)

3. El peor de los casos
Para encontrar el carácter en la última posición de la cadena, entonces:
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

En el peor de los casos, debido a que se retiene el orden superior y se elimina n/2 (el primer elemento) y se ignora el coeficiente (el segundo elemento), está ON^2

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

Cuando n = 2, el número de ejecuciones es 1
Cuando n = 4, el número de ejecuciones es 2
Cuando n = 16, el número de ejecuciones es 4
Suponiendo que el número de ejecuciones es x, entonces 2
x = n
Por tanto el número de ejecuciones: x = log n
Por lo tanto: la complejidad temporal de func5 en el peor de los casos es:
O(log2^n)

Diferentes libros tienen diferentes métodos de expresión. Los métodos de escritura anteriores no son muy diferentes. Recomendamos usar log n.

complejidad espacial

Lo que cabe señalar sobre la complejidad del espacio es que su representación de cálculo también está representada por O, y sus reglas siguen las mismas tres reglas que la complejidad del tiempo.

Aviso

El espacio de pila requerido cuando la función se está ejecutando (almacenamiento de parámetros, variables locales, cierta información de registro, etc.) se ha determinado durante la compilación, por lo que la complejidad del espacio está determinada principalmente por el espacio adicional solicitado explícitamente por la función cuando se está ejecutando. .

Ejemplo 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

El marco de la pila de funciones se determinó durante la compilación.
Solo necesitas prestar atención al espacio adicional solicitado por la función durante el tiempo de ejecución.
El espacio de aplicación adicional para BubbleSort es
Hay un número limitado de variables locales, como el intercambio, que utiliza una cantidad constante de espacio adicional.
Entonces la complejidad del espacio es O(1)