Mi información de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Hay muchas formas y métodos en el proceso de completar el mismo problema de algoritmo. El resultado final es el mismo y correcto, pero la eficiencia puede variar.
Al igual que partir de un mismo lugar y llegar a otro lugar, las formas de llegar al lugar incluyen aviones, trenes, coches particulares... pero el tiempo que se tarda es diferente y la economía también es diferente.
Una vez que el algoritmo se escribe en un programa ejecutable, requiere recursos de tiempo y recursos de espacio (memoria) para ejecutarse. Por lo tanto, la calidad de un algoritmo generalmente se mide desde dos dimensiones: tiempo y espacio, es decir, complejidad temporal y complejidad espacial.
La complejidad del tiempo mide principalmente qué tan rápido se ejecuta un algoritmo, mientras que la complejidad del espacio mide principalmente el espacio adicional requerido para ejecutar un algoritmo.
En los primeros días del desarrollo informático, las computadoras tenían una capacidad de almacenamiento muy pequeña. Por eso nos preocupamos mucho por la complejidad del espacio. Sin embargo, tras el rápido desarrollo de la industria informática, la capacidad de almacenamiento de las computadoras ha alcanzado un nivel muy alto. Así que ahora ya no necesitamos prestar especial atención a la complejidad espacial de un algoritmo.
Cuando juego algunos juegos, mi teléfono se calienta mucho cuando juego, y algunos juegos no se calientan si los juego, lo cual es inseparable de la complejidad. Mi teléfono ejecuta un algoritmo simple y se ejecuta rápidamente, pero. Es complicado de ejecutar el algoritmo, para asegurar que el tiempo se use menos, se debe habilitar la potencia máxima, por lo que se calentará.
Definición: En informática, la complejidad temporal de un algoritmo es una fórmula funcional T (N), que describe cuantitativamente el tiempo de ejecución del algoritmo. La complejidad del tiempo mide la eficiencia del tiempo de un programa, entonces, ¿por qué no calcular el tiempo de ejecución del programa?
- Debido a que el tiempo de ejecución del programa está relacionado con la configuración del entorno de compilación y la máquina en ejecución, por ejemplo, si un programa de algoritmo se compila con un compilador antiguo o con un compilador nuevo, el tiempo de ejecución será diferente en la misma máquina.
- 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.
- 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.
Por lo tanto, al juzgar el grado de asignación de tiempo de un algoritmo, no se considera el tiempo para ejecutar el algoritmo, solo el número de instrucciones ejecutadas.
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;
}
}
A través de la observación:
Número de operaciones básicas realizadas por Func1:
T(N)=N2+ 2*N+ 10
En la práctica, cuando calculamos la complejidad del tiempo, no calculamos el número exacto de ejecuciones del programa. Calcular el número exacto de ejecuciones sigue siendo muy problemático (diferentes oraciones del código del programa tendrán diferentes números de instrucciones compiladas (como). esto), calcular el número exacto de ejecuciones tiene poca importancia, porque solo queremos comparar el nivel de crecimiento del programa del algoritmo al calcular la complejidad del tiempo, es decir, la diferencia en T (N) cuando N continúa aumentando. Hemos visto anteriormente que las constantes y los términos de bajo orden tienen poco impacto en los resultados cuando N continúa creciendo, por lo que solo necesitamos calcular el número aproximado de ejecuciones que el programa puede representar para aumentar el orden de magnitud. usualmente usado Use la notación asintótica de Big O.
La complejidad del espacio también es una expresión matemática, que es el espacio adicional asignado temporalmente debido a las necesidades del algoritmo durante la operación de un algoritmo.
La complejidad del espacio no es cuántos bytes de espacio ocupa el programa. Debido a que en circunstancias normales, el tamaño de cada objeto no diferirá mucho, la complejidad del espacio se calcula por la cantidad de variables.
Las reglas de cálculo de la complejidad espacial son básicamente similares a las de la complejidad práctica, y también se utiliza la notación asintótica Big O.
Nota: 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 determinó 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 durante el tiempo de ejecución. . Seguro
El espacio no es una consideración clave en el desarrollo informático actual, pero se debe evitar un desperdicio excesivo que causará problemas innecesarios.
Notación O grande: es un símbolo matemático utilizado para describir el comportamiento asintótico de funciones.
Reglas para pasar a la notación asintótica Big 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 inferior en los resultados es cada vez menor y, cuando N es infinito, pueden ignorarse.- 2. Si el término de mayor orden existe y no es 1, elimine el coeficiente constante de este término, porque a medida que N continúa aumentando, este coeficiente
El impacto en los resultados es cada vez menor y cuando N es infinito, se puede ignorar.- 3. Si no hay N elementos relacionados en T(N) sino solo elementos constantes, reemplace todas las constantes aditivas con la constante 1.
Peor de los casos: número máximo de ejecuciones (límite superior) para cualquier tamaño de entrada
Caso promedio: número esperado de ejecuciones para cualquier tamaño de entrada
Mejor caso: número mínimo de ejecuciones (límite inferior) para cualquier tamaño de entrada
En la práctica, la representación asintótica de Big O generalmente se centra en el límite superior del algoritmo, que es la peor situación operativa.
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;
}
}
complejidad del tiempo:
Omita el código que se ejecuta una vez, como count=0, este código.
Mantenga la cantidad de ejecuciones de código que tienen un gran impacto en el tiempo de ejecución.
El número de ejecuciones del primer ciclo es una ejecución de doble ciclo de Nnorte
El segundo bucle es una capa de tiempos de ejecución de bucle 2norte
El tercer ciclo es 10 veces.
La suma del número de ejecuciones es T(N)=N2+2*N+10
Big O representa la complejidad del tiempo, descarta el pequeño impacto y toma el límite.
EN2)
Complejidad espacial:
La función Func1 se aplica para el tamaño del espacio. Por ejemplo, int count = 0, se aplica para el tamaño de espacio del tipo int M=10, también se aplica para el espacio del tipo int.
Estos dos espacios también se utilizan en el bucle sin espacio de aplicación adicional.
El tamaño del espacio de la aplicación es constante.
La complejidad espacial expresada en Big O es:
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);
}
complejidad del tiempo:
La cantidad de veces que se ejecuta el código es mayor que el primer ciclo, que es N*2.
El segundo bucle se ejecuta 10 veces.
Utilice O grande para representar la complejidad del tiempo. El mayor impacto es 2 * N. Se omite el término del coeficiente anterior:
EN)
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);
}
complejidad del tiempo
Hay dos incógnitas y el mayor impacto se produce en los dos bucles.
El primer bucle se ejecuta M veces.
El segundo ciclo se ejecuta N veces.
Debería ser un número desconocido. No estoy seguro de cuál es mayor y cuál es menor. No lo omitiré.
O(M+N)
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%dn", count);
}
complejidad del tiempo:
El mayor impacto aquí es un ciclo.
El número de veces que se ejecuta el bucle es 100.
es una constante fija
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;
}
La función que logra esta función es encontrar el subíndice de un carácter en una matriz.
El número de carreras aquí es incierto.
Es posible encontrar F(N)=1 de una vez
Es posible encontrar F(N)=N/2 en el medio
Se puede encontrar al final, o se devuelve NULL si no se encuentra, F (N) = N
Big O toma el peor de los casos:
La complejidad del tiempo es O (N)
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
Este número de ejecuciones está relacionado con el tamaño de n, pero no se repite n veces. Debería ser porque la variable del bucle se multiplicará por 2 durante el bucle y el bucle saltará rápidamente después de ejecutarse diez veces. El valor de la variable de bucle cnt alcanzará 1024.
Suponiendo que el número de ciclos es x, entonces 2X=n
x=logn
Entonces la complejidad del tiempo es: 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 función completa la clasificación ascendente de burbujas.
Hay un bucle aquí. Este bucle es un bucle anidado de dos niveles.
El número de bucles no está definido.
El peor de los casos es que el bucle externo se ejecute n veces.
Entonces el bucle interno se ejecutará (n-1)+(n-2)+(n-3)+……+2+1+0
es una secuencia aritmética y la suma es:
La complejidad del tiempo es: O (N)
Complejidad espacial:
No hay espacio de aplicación adicional y el espacio aplicado es constante.
O(1)
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
complejidad del tiempo:
Recursado N veces
Entonces la complejidad del tiempo es: O(N)
Complejidad espacial:
Cada vez que recurre, debe solicitar un espacio.
Recurrió N veces y aplicó N veces de espacio.
La complejidad del espacio es: O (N)
Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.
Correo[email protected]