Algoritmos y su complejidad. Complejidad algorítmica. Algoritmos de búsqueda. Algoritmos de clasificación. Complejidad capacitiva con criterio de peso uniforme.

Probablemente te hayas topado con notaciones como O(log n) más de una vez o hayas escuchado frases como “complejidad computacional logarítmica” dirigidas a algunos algoritmos. Y si aún no entiendes lo que esto significa, este artículo es para ti.

Calificación de dificultad

La complejidad de los algoritmos generalmente se mide por su tiempo de ejecución o uso de memoria. En ambos casos, la complejidad depende del tamaño de los datos de entrada: una matriz de 100 elementos se procesará más rápido que una similar de 1000. Sin embargo, pocas personas están interesadas en el tiempo exacto: depende del procesador, el tipo de datos , lenguaje de programación y muchos otros parámetros. Sólo es importante la complejidad asintótica, es decir, la complejidad cuando el tamaño de los datos de entrada tiende a infinito.

Digamos que algún algoritmo necesita realizar 4n 3 + 7n operaciones condicionales para procesar n elementos de datos de entrada. A medida que n aumenta, el tiempo de funcionamiento final se verá significativamente más afectado elevando n a un cubo que multiplicándolo por 4 o sumando 7n. Luego dicen que la complejidad temporal de este algoritmo es O(n 3), es decir, depende cúbicamente del tamaño de los datos de entrada.

El uso de la O mayúscula (o la llamada notación O) proviene de las matemáticas, donde se utiliza para comparar el comportamiento asintótico de funciones. Formalmente, O(f(n)) significa que el tiempo de ejecución del algoritmo (o la cantidad de memoria ocupada) crece dependiendo del tamaño de los datos de entrada no más rápido que alguna constante multiplicada por f(n) .

Ejemplos

O(n) - complejidad lineal

Por ejemplo, el algoritmo para encontrar el elemento más grande en una matriz sin clasificar tiene esta complejidad. Tendremos que revisar los n elementos de la matriz para entender cuál es el máximo.

O(log n) - complejidad logarítmica

El ejemplo más simple es la búsqueda binaria. Si la matriz está ordenada, podemos verificar si contiene un valor particular usando el método de reducción a la mitad. Comprobemos el elemento del medio, si es más grande que el que estamos buscando, descartaremos la segunda mitad de la matriz; definitivamente no está allí. Si es menor, viceversa: descartaremos la mitad inicial. Y así continuaremos dividiendo por la mitad, y al final comprobaremos log n elementos.

O(n 2) - complejidad cuadrática

Por ejemplo, el algoritmo de ordenación por inserción tiene esta complejidad. En la implementación canónica, consta de dos bucles anidados: uno para recorrer toda la matriz y el segundo para encontrar el lugar para el siguiente elemento en la parte ya ordenada. Por tanto, el número de operaciones dependerá del tamaño de la matriz como n * n, es decir n 2.

Hay otras clasificaciones de dificultad, pero todas se basan en el mismo principio.

También sucede que el tiempo de ejecución del algoritmo no depende en absoluto del tamaño de los datos de entrada. Entonces la complejidad se denota como O(1). Por ejemplo, para determinar el valor del tercer elemento de una matriz, no es necesario recordar los elementos ni repasarlos muchas veces. Siempre solo necesita esperar el tercer elemento en el flujo de datos de entrada y este será el resultado, que lleva el mismo tiempo calcular para cualquier cantidad de datos.

Lo mismo ocurre con las evaluaciones de la memoria cuando esto es importante. Sin embargo, los algoritmos pueden utilizar mucha más memoria que otros al aumentar el tamaño de los datos de entrada, pero aún así se ejecutan más rápido. Y viceversa. Esto ayuda a elegir las mejores formas de resolver problemas en función de las condiciones y requisitos actuales.

Ya sabemos que la corrección no es la única cualidad que debe tener un buen programa. Uno de los más importantes es la eficiencia, que caracteriza principalmente plazo de entrega programas para varios datos de entrada (parámetro).

Encontrar la dependencia exacta de un programa específico es una tarea bastante difícil. Por este motivo, suelen ser limitados. estimaciones asintóticas esta función, es decir, una descripción de su comportamiento aproximado para valores grandes del parámetro. A veces, para estimaciones asintóticas utilizan la relación tradicional (léase "O grande") entre dos funciones. , cuya definición se puede encontrar en cualquier libro de texto sobre análisis matemático, aunque se usa con mayor frecuencia relación de equivalencia(léase "theta grande"). Su definición formal está, por ejemplo, en el libro, aunque por ahora nos bastará con entender esta cuestión en términos generales.

Como primer ejemplo, volvamos a los programas que acabamos de analizar para encontrar el factorial de un número. ¡Es fácil ver que el número de operaciones que se deben realizar para encontrar el factorial! Los números en una primera aproximación son directamente proporcionales a este número, porque el número de repeticiones del bucle (iteraciones) en este programa es igual a . En tal situación, se acostumbra decir que el programa (o algoritmo) tiene complejidad lineal(dificultad o ).

¿Es posible calcular factorial más rápido? Resulta que si. Es posible escribir un programa que dé el resultado correcto para los mismos valores que dan todos los programas anteriores, sin utilizar iteración ni recursividad. Su complejidad será , lo que en realidad significa organizar los cálculos de acuerdo con alguna fórmula sin usar bucles ni llamadas recursivas.

No menos interesante es el ejemplo de calcular el número de Fibonacci. En el proceso de investigación ya se descubrió que su complejidad es exponencial e igual a . Estos programas prácticamente no son aplicables en la práctica. Es muy fácil verificar esto intentando calcular el número número 40 de Fibonacci usándolo. Por esta razón, la siguiente tarea es bastante relevante.

Problema 5.4 complejidad lineal.

Aquí tienes una solución a este problema en el que las variables j y k contienen los valores de dos números de Fibonacci consecutivos.

Texto del programa

clase pública FibIv1 (public static void main(String args) lanza una excepción (int n = Xterm.inputInt("Ingrese n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j);

) ) )

La siguiente pregunta es bastante natural: ¿es posible encontrar los números de Fibonacci aún más rápido?

Después de estudiar ciertas ramas de las matemáticas, es bastante sencillo derivar la siguiente fórmula para el número de Fibonacci, que es fácil de comprobar para valores pequeños:

Texto del programa

Podría parecer que, basándose en ello, sería fácil escribir un programa con complejidad que no utilice iteración ni recursividad.

clase pública FibIv2 (public static void main(String args) lanza excepción (int n = Xterm.inputInt("Ingrese n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5 Xterm.println("f(" + n + ") = " + j) ) Este programa en realidad utiliza una llamada a la función de exponenciación ( Math.pow(f,n) ), que no se puede implementar en un tiempo más rápido que el logarítmico (). Se dice que los algoritmos en los que el número de operaciones es aproximadamente proporcional (en informática es costumbre no indicar la base del logaritmo binario) tienen ().

complejidad logarítmica

Para calcular el número de Fibonacci, existe un algoritmo de este tipo, cuya implementación de software daremos sin comentarios adicionales; de lo contrario, será necesario explicar demasiado (la conexión entre los números de Fibonacci y las potencias de una determinada matriz de orden dos, el uso de clases para trabajar con matrices, un algoritmo para elevar rápidamente una matriz a una potencia) . Problema 5.5 complejidad logarítmica.

Texto del programa

clase pública FibIv3 (public static void main(String args) lanza excepción (int n = Xterm.inputInt("Ingrese n -> "); Xterm.print("f(" + n + ")"); if (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( if ((n&1) == 0) ( n >>>= 1; c.square(); ) else ( n -= 1; b.mul(c); ) ) Xterm.println(" = " + b.fib());

) ) ) clase Matriz ( privada larga a, b, c, d; matriz pública (larga a, larga b, larga c, larga d) ( this.a = a; this.b = b; this.c = c; this.d = d; public void mul(Matriz m) ( long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+ d *m.c; largo d1 = c*m.b+d*m.d; (retorno b;))

Si intenta calcular el número diez millones de Fibonacci utilizando este programa y los anteriores, la diferencia en el tiempo de cálculo será bastante obvia. Desafortunadamente, el resultado será incorrecto (en ambos casos) debido al rango limitado de números largos.

En conclusión, presentamos una tabla comparativa de tiempos de ejecución de algoritmos con diferente complejidad y explicamos por qué, a medida que aumenta la velocidad de la computadora, aumenta significativamente la importancia de utilizar algoritmos rápidos.

Consideremos cuatro algoritmos para resolver el mismo problema, que tienen complejidades , y , respectivamente. Supongamos que el segundo de estos algoritmos requiere exactamente un minuto de tiempo para ejecutarse en alguna computadora con el valor del parámetro. Entonces, el tiempo de ejecución de estos cuatro algoritmos en la misma computadora para diferentes valores de parámetros será aproximadamente el mismo que 10 300000 años.

Cuando los programadores novatos prueban sus programas, los valores de los parámetros de los que dependen suelen ser pequeños. Por lo tanto, incluso si se utilizó un algoritmo ineficaz al escribir un programa, esto puede pasar desapercibido. Sin embargo, si intenta aplicar un programa de este tipo en condiciones reales, inmediatamente aparecerá su inadecuación práctica. A medida que aumenta la velocidad de las computadoras, también aumentan los valores de los parámetros para los cuales la operación de un algoritmo en particular se completa en un tiempo aceptable. Por tanto, aumenta el valor medio de y, en consecuencia, la relación entre los tiempos de ejecución de los algoritmos rápido y lento.!

Cuanto más rápida sea la computadora, mayor será la pérdida relativa cuando se utilice un algoritmo incorrecto

Capítulo 2. Complejidad de los algoritmos.

2.1 Tiempo y complejidad computacional de los algoritmos. (Complejidad temporal del algoritmo.(t) norte t– tamaño del problema) es el tiempo de ejecución de un algoritmo, medido en pasos (instrucciones del algoritmo que deben ejecutarse para lograr un resultado). Es decir, este es el número de operaciones elementales que componen el algoritmo para resolver el problema (:=,<>, =, +, –, *, /; y, o, no, xor; llamar, regresar).

Hay tres tipos de complejidad temporal, que dependen de la combinación de datos de entrada al resolver un problema (equivalencia, escasez, ordenamiento y otras propiedades de los datos de entrada).

https://pandia.ru/text/78/183/images/image002_151.gif" ancho="178 altura=60" altura="60">

Acontecimiento Complejidad temporal del algoritmo.(t)= do* t2 aplicable a una matriz cuadrada.

Las operaciones elementales en este caso son una combinación de “+” y “*”.

Si la matriz original es identidad, obtenemos el mejor caso.

Si la mitad de los elementos de la matriz son 0 y la otra mitad son 1, obtenemos el caso promedio.

Constante CON, que no se puede expresar con precisión, caracteriza la influencia de factores externos en el tiempo de ejecución de los algoritmos (velocidad de la computadora, velocidad de compilación). Por lo tanto, utilizar unidades de tiempo para estimar la complejidad temporal de los algoritmos no es del todo correcto. En este caso, se dice que la complejidad temporal del algoritmo de multiplicación matriz-vector es proporcional a t2 .

2.2 ohy Ω – notaciones.

El comportamiento de la complejidad del tiempo al aumentar. t (t® ¥ ) llamado Complejidad asintótica del algoritmo.

Para describir la tasa de crecimiento de la complejidad asintótica, utilizamos Notación O. Cuando dicen que la complejidad temporal de un algoritmo es del orden t2 :

Complejidad temporal del algoritmo.(t)= oh(t2 )= oh(F(t)),

Esto implica que hay constantes positivas. do, n0=constante (do>0), tal que para todos t ³ t0 la desigualdad se mantiene

Complejidad temporal del algoritmo.(t) £ do* F(t)

Este es el límite superior de la estimación de complejidad.

Ejemplo 2:

Dejar T(0)=1, T(1)=4, …, T(t)=(t+1)2, entonces la complejidad temporal de este algoritmo tiene el orden de crecimiento Complejidad temporal del algoritmo.(t)= oh(t2 ).

Se puede demostrar que para todos t > norte0 en norte0 = 1, do = 4 Se satisface la desigualdad (1).

(t+1)2 £ 4* t2

Ejemplo 3:

Si la complejidad del tiempo se escribe como un polinomio

Complejidad temporal del algoritmo.(t)= do1 t2 + do2 t+ do3 ,

entonces dicho algoritmo tiene un orden de complejidad que es múltiplo del grado del elemento máximo del polinomio, ya que crece más rápidamente cuando t® ¥ :

Complejidad temporal del algoritmo.(t)= oh(t2 ).

Por ejemplo:

3 norte2 +5 norte+1 £ 5 norte2

" norte ³ 1

Ejemplo 4:

Si algún algoritmo tiene una complejidad que es múltiplo de 3 norte, entonces se puede demostrar que el orden de aumento de la velocidad no puede ser múltiplo oh(2 norte):

Complejidad temporal del algoritmo.(t)=3 norte¹ oh(2 norte).

Que haya constantes do, norte0 , tal que se cumple la siguiente desigualdad:

3norte £ do*2 norte, norte > norte0 .

De aquí obtenemos:

CON³ (3/2)2, norte > norte0 .

pero cuando norte® ¥ no existe tal constante CON, lo que satisfaría esta desigualdad.

Además del límite superior de complejidad, también existe un límite inferior de la tasa de crecimiento de la complejidad del tiempo:

Complejidad temporal del algoritmo.(t) ³ W.(F(t))

La desigualdad (2) implica que hay alguna constante CON, para lo cual en t® ¥ complejidad del tiempo

Complejidad temporal del algoritmo.(t) ³ do* F(t).

Dada la dificultad de determinar con precisión T(N) (complejidad temporal asintótica), dependiendo del tamaño de los datos iniciales, en la práctica se utilizan límites inferior y superior de la complejidad temporal del algoritmo:

Complejidad temporal del algoritmo.(t) = q (F(t))

Dependiendo del valor de la constante CON el ritmo al que crece la complejidad del algoritmo puede variar significativamente.

Ejemplo 5:

Deje que la complejidad del tiempo se escriba mediante la fórmula.

T(N)=3n2 –100n+6=O(n2)

3n2 >3n2 –100n+6, n³ 1,C=3.

Si C1» 0 (C1=0,00001), entonces la desigualdad

10-5 norte2 > 3 norte2 –100 norte+6, norte³ 1

no se ejecuta.

Pero se puede demostrar que el orden de complejidad creciente

3n2 –100n+6¹ EN).

C*N< 3N2, N>DO.

3n2 –100n+6=(n2)

do=2.29, norte ³ norte0.

2.99* norte2 < 3 norte2 –100 norte+6

Se puede demostrar que el límite inferior

3 norte2 –100 norte+6 ¹ W.(norte3 ) en C=1.

Desigualdad 3 norte2 –100 norte+6 ³ norte3 no se ejecuta.

3 norte2 –100 norte+6= W.(norte)

do1 = , norte> norte0 .

https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src=">

F1 (t)=100 norte2

F2 (t)=5 norte3

norte0 =20 – punto crítico.

Otra razón para preferir algoritmos con menor orden de complejidad es que cuanto menor sea el orden de complejidad, mayor será el tamaño del problema. t se puede resolver prácticamente.

0 " estilo="margin-left:5.4pt;border-collapse:collapse;border:none">

norte!

Ejemplo 6:

Debe tenerse en cuenta que un orden superior de crecimiento en la complejidad de los algoritmos suele tener una constante menor C1 en comparación con el pequeño orden de crecimiento de la complejidad, caracterizado por la constante C2.

En este caso, un algoritmo con una complejidad que aumenta rápidamente puede ser preferible para resolver problemas con tamaños de datos pequeños ( norte® 0 ).

Se dan cinco algoritmos para resolver el mismo problema, cada uno con complejidad:

A1: 100 t

A2: 100 t* iniciar sesión

A3: 10 t2

A4: t3

A5: 2 t

Entonces por problemas con t=2 ¸ 9 A5 será más rápido ( F(t) ~ 4 ¸ 512 ). Otros algoritmos darán resultados significativamente más bajos al realizar la sustitución.

En t=10 ¸ 58 A3 parece ser preferible.

En t=59 ¸ 1024 A2 será el más efectivo.

En t>1024 Se prefiere A1.

Para programas que constan de varios algoritmos ejecutados secuencialmente o en paralelo, la complejidad se estima mediante regla de la suma Y regla de productos.

Regla de la suma : Deje que el programa consta de dos algoritmos P1 y P2 ejecutados secuencialmente, para los cuales se determina la complejidad. oh(F(norte)) Y oh(gramo(norte)) respectivamente. Luego, la complejidad temporal de todo el programa se determinará como la suma de las complejidades temporales de cada uno de los algoritmos:

Complejidad temporal del algoritmo.(norte) = Complejidad temporal del algoritmo.1 (norte)+ Complejidad temporal del algoritmo.2 (norte)

En el caso general obtenemos:

Tennesse)Þ O(máx f(n), g(n))

Regla de obras: Sea la complejidad temporal de un programa que consta de dos algoritmos de ejecución paralela que tienen el orden de complejidad oh(F(norte)) Y oh(gramo(norte)) en consecuencia, se define como el producto de las complejidades temporales de cada uno de los algoritmos:

Complejidad temporal del algoritmo.(norte) = Complejidad temporal del algoritmo.1 (norte)* Complejidad temporal del algoritmo.2 (norte)

En general:

Complejidad temporal del algoritmo.(norte) Þ oh(F(norte)* gramo(norte))

Logaritmos.

2.3. Recursión.

La complejidad de los algoritmos recursivos es difícil de evaluar debido al anidamiento de estructuras algorítmicas.

F(norte) Þ F(norte* F(norte-1))

Por ejemplo, para evaluar recursivamente el algoritmo n! La complejidad dependerá de la complejidad de cada uno de los algoritmos incluidos en la recursividad.

En general Complejidad temporal del algoritmo.(norte) ~ oh(t).

Otros algoritmos recursivos generalmente tienen complejidad temporal. Complejidad temporal del algoritmo.(norte) ~ oh(un) norte a= constante, lo que resulta en una complejidad total mayor que la complejidad de un algoritmo no recursivo para resolver el mismo problema.

2.4 Evaluación de la complejidad de algoritmos y programas.

2.4.2 Algoritmos de recuperación de dependencias.

En algunos casos, se desconoce la estructura del programa y sólo es posible determinar el tiempo que se ejecutará para diferentes tamaños de datos de entrada. Complejidad temporal del algoritmo.(t) (segundo.)

Para construir una dependencia analítica de la complejidad del programa, evalúe la función. Complejidad temporal del algoritmo.(t) en algún intervalo [ Nmín, Nmáx] . Luego se aproxima la curva encontrada de alguna función analítica, cambiando los parámetros de la función y estimando el error de aproximación.

Como regla general, se utilizan las conocidas funciones de complejidad temporal como tales: oh(norte!), oh(XN), oh(NX), oh(iniciar sesión), oh(https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">Como resultado de un experimento con el programa, se creó una tabla de dificultades temporales obtenido:

Como resultado de la búsqueda de una aproximación de la función, se obtuvo la siguiente dependencia analítica:

https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src=">

Ejemplo 2:

A menudo sucede que el tiempo de ejecución de un mismo algoritmo, además del tamaño del problema, está influenciado por otros parámetros ingresados ​​por el usuario.

En este caso, se construye una familia de funciones de aproximación y se encuentra analíticamente la complejidad del algoritmo.

Intensidad laboral" href="/text/category/trudoemkostmz/" rel="bookmark">intensidad laboral (tiempo de trabajo).

La naturaleza polinómica o exponencial del algoritmo es invariante con respecto a la forma de representación de los datos de entrada (binario, decimal u otro sistema numérico).

Se dice que un algoritmo es polinomio si su tiempo de ejecución, es decir, su complejidad temporal, está limitada por un polinomio de algún grado. Complejidad temporal del algoritmo.(t)= oh(Nuevo Méjico) . Entonces, todos los problemas que se resuelven mediante dicho algoritmo forman una clase P de problemas. Dicen que estas tareas están incluidas en R.

Problemas cuya complejidad temporal es exponencial ( Complejidad temporal del algoritmo.(t)= oh(kt) ), no están incluidos en R.

Comentario : Se puede demostrar que los problemas con complejidad lineal están incluidos en P

Complejidad temporal del algoritmo.(t)= oh(t1 )

Introduzcamos una clase de problemas NP que se pueden resolver en tiempo polinómico utilizando un algoritmo no determinista.

Definamos el estado del algoritmo como la combinación de la dirección del comando que se está ejecutando actualmente y los valores de todas las variables, lo que equivale al vector de estado del proceso. Por lo tanto, la mayoría de los algoritmos son deterministas, es decir, en ellos, para cualquier estado, solo hay un siguiente estado válido (incluidas las operaciones condicionales y de selección). Esto significa que dicho algoritmo puede hacer una cosa a la vez.

EN algoritmo no determinista (NDA) para cualquier estado dado puede haber más de un siguiente estado admisible, es decir, dicho algoritmo puede ejecutar más de una declaración en un momento dado.

NDA no es un algoritmo aleatorio o probabilístico. Es un algoritmo que puede estar en muchos estados (esto equivale a resolver un problema con muchas opciones en paralelo).

Ejemplo:

Un algoritmo determinista (DA) resolvería este problema de forma secuencial (buscar entre todas las opciones, comparar con el criterio de optimización K0 hasta elegir la alternativa A0).

NDA puede recibir simultáneamente (en paralelo) todas las alternativas y compararlas con K0, copiándose a sí misma como un proceso separado para cada alternativa, que se ejecuta de forma independiente.

Además, si alguna copia detecta que se ha recibido un resultado incorrecto o no se ha recibido ningún resultado, deja de ejecutarse. Si la copia encuentra una solución que satisface K0, declara éxito y todas las demás copias dejan de funcionar.

Eso. NDA se caracteriza por tres parámetros:

1. elección– una función multivaluada cuyos valores son elementos del conjunto S;

2. falla hace que una copia del algoritmo deje de ejecutarse;

3. éxito hace que todas las copias del algoritmo dejen de ejecutarse y produzcan un resultado.

Obviamente, ningún dispositivo físico es capaz de tener un comportamiento no determinista ilimitado, lo que significa que la NDA es un método teórico.

Los problemas que se pueden resolver utilizando NDA polinomial forman una clase de problemas NP.

2.5.2 notario público-difícil ynotario público- completar tareas.

El problema incluido en P es notario público-difícil, si existe un polinomio DA (PDA) de su solución, que se puede utilizar para obtener soluciones a todos los problemas incluidos en NP. Es decir, un problema es NP-difícil si es al menos tan difícil como cualquier problema NP.

Un problema NP-difícil que pertenece a NP se llama notario público-lleno tarea. Estos problemas no son menos difíciles que cualquier problema NP. Además, la existencia de un PDA para un problema NP-difícil o NP-completo significa que las clases P y NP coinciden, es decir, es posible resolver todos los problemas de tercera clase utilizando un algoritmo rápido.

Para demostrar que un problema es NP-difícil, es necesario demostrar que si existe un PDA para el problema, entonces se puede utilizar para obtener otro PDA para resolver problemas incluidos en NP.

Para establecer que un problema es NP-completo, es necesario demostrar que pertenece a NP.

La idea de utilizar un algoritmo para resolver un problema para obtener un algoritmo para resolver otro es una de las más importantes en la teoría de los algoritmos.

Definición 1: El problema P1 se transforma en la tarea P2 si cualquier caso especial del problema P1 se puede transformar en tiempo polinomial en algún caso especial del problema P2. Entonces la solución P1 se puede obtener en tiempo polinomial a partir de la solución a un caso especial del problema P2.

https://pandia.ru/text/78/183/images/image024_39.gif" ancho="158 altura=56" altura="56">

Por ejemplo:

F2 (xi)=(incógnita1 Ú incógnita2 ) Ù ( ) Ù ()

no es factible, porque por cualquier xi F2 (xi)= FALSO.

Teorema :

El problema de satisfacibilidad es NP-completo.

selección xi (verdadero, falso)

si E(x1, x2,…, xN) entonces éxito

más fracaso

Utilizando la transformación del problema P1 a P2, se puede demostrar que incluso el caso limitado del problema de satisfacibilidad es NP-completo.

K-factibilidad .

K-satisfacibilidad significa que cualquier cláusula incluida en CNF contiene como máximo K variables lógicas.

Caso mínimo K=3. Para una función booleana representada en CNF, en tiempo polinomial se puede encontrar la función E*(x2), que no contenga más de tres variables en cada cláusula. Entonces mi factible si es factible MI*.

mi* (incógnita1 , incógnita2 ,…, xn) ® mi* (xi)

Para hacer esto, use el método de reducir el orden de la cláusula.

(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )

Utilizando un proceso de descomposición iterativo, se puede obtener MI*.

Encuentra el algoritmo de solución. MI* más simple que las funciones mi. Pero al mismo tiempo demostrar la viabilidad. MI*, demostramos la satisfacibilidad de la función original mi.

Caso especial: para K=2 la función mi incluido en r.

Ejemplos de problemas de clase NP también pueden incluir problemas graficos :

1) Determinar las camarillas máximas de un gráfico no dirigido (problema NP-difícil).

2) El problema de determinar un subgrafo completo (problema NP-completo).

3) Determinación de la cobertura de vértices de cardinalidad L para un gráfico no dirigido (problema NP-completo).

4) Determinar las coberturas máximas de vértices de un gráfico no dirigido (problema NP-difícil).

5) El problema de determinar la existencia de un ciclo hamiltoniano para un gráfico (problema NP-completo).

6) Problema del viajante: determinar el movimiento óptimo a lo largo de un gráfico con una única entrada en cada vértice (problema NP-difícil).

7) Problema de programación (problema NP-completo).

2.6 Problemas algorítmicamente irresolubles

Compartir problemas soltero Y masivo.

Por ejemplo:

5+7=? - único problema.

x+y=? - un problema enorme.

Los algoritmos para obtener objetos paradójicos o resolver problemas de los que se derivaría la existencia de objetos paradójicos deberían ser fundamentalmente irresolubles.

Por ejemplo, las paradojas son:

Ejemplo 1:

El décimo problema de Hilbert.

D. Hilbert en 1901, al resolver ecuaciones diofánticas, planteó un problema que establece:

Encuentre un algoritmo que determine alguna solución entera para una ecuación diofántica arbitraria

F(incógnita, y, …)=0

Este es un polinomio con exponentes enteros y coeficientes enteros para incógnitas.

anxn+an-1xn-1+…+a2x2+a1x+a0=0

Para la ecuación anterior existe una solución particular, que es que cada raíz entera xi es un divisor a0 . Al mismo tiempo a0 descompóngalo en factores primos y verifique la correspondencia de cada factor con la raíz.

En 1970, el matemático de Leningrado Yu Matiyasevich demostró matemáticamente la imposibilidad algorítmica de resolver la ecuación diofántica en forma general.

Ejemplo 2:

Teorema de Fermat:

No existen tales números enteros a, b, s, norte (norte>2) , para lo cual se cumple la igualdad

un + mn = cn

Este teorema ha sido probado para muchos valores. norte y se ha verificado para casos especiales, pero aún no se ha creado una demostración general del teorema.

Ejemplo 3:

El problema de Goldbach.

H. Holbach formuló el problema en una carta a Euler en 1742:

Demuestre que todo número entero t³ 6 se puede representar como la suma de tres números primos

t= a+ b+ do

Esto significa que necesitamos encontrar un algoritmo que permita cualquier número entero. t³ 6 Encuentre al menos una descomposición en tres términos simples.

Euler propuso una solución frecuente a este problema: incluso t este problema tiene solución y equivale a la descomposición en dos términos simples.

I. Vinogradov demostró en 1937 que por impar t Se pueden encontrar tres términos primos, pero para los números pares aún no se ha encontrado una solución.

Es tradicional evaluar el grado de complejidad de un algoritmo por la cantidad de recursos informáticos básicos que utiliza: tiempo de procesador y RAM. En este sentido, se introducen conceptos como complejidad temporal de un algoritmo y complejidad volumétrica de un algoritmo.

El parámetro de complejidad del tiempo se vuelve especialmente importante para problemas que involucran la operación de programas interactivos o para problemas de control en tiempo real. A menudo, un programador que crea un programa de control para algún dispositivo técnico tiene que encontrar un equilibrio entre la precisión de los cálculos y el tiempo de ejecución del programa. Normalmente, una mayor precisión conduce a un mayor tiempo.

La complejidad volumétrica de un programa se vuelve crítica cuando el volumen de datos que se procesa alcanza el límite de la capacidad de RAM de la computadora. En las computadoras modernas, la gravedad de este problema se reduce tanto debido al aumento en la cantidad de RAM como al uso efectivo de un sistema de almacenamiento multinivel. El programa tiene acceso a un área de memoria muy grande y prácticamente ilimitada (memoria virtual). La falta de memoria principal sólo provoca cierta ralentización debido a los intercambios con el disco. Se utilizan técnicas para minimizar la pérdida de tiempo durante dicho intercambio. Este es el uso de la memoria caché y la visualización por hardware de las instrucciones del programa para la cantidad requerida de movimientos hacia adelante, lo que le permite transferir los valores requeridos del disco a la memoria principal por adelantado. Con base en lo anterior, podemos concluir que minimizar la complejidad capacitiva no es una tarea prioritaria. Por lo tanto, en el futuro estaremos interesados ​​principalmente en la complejidad temporal de los algoritmos.

El tiempo de ejecución del programa es proporcional al número de operaciones ejecutadas. Por supuesto, en unidades de tiempo (segundos), también depende de la velocidad del procesador (frecuencia de reloj). Para que el indicador de complejidad temporal del algoritmo sea invariante con respecto a las características técnicas de la computadora, se mide en unidades relativas. Normalmente, la complejidad del tiempo se mide por la cantidad de operaciones realizadas.

Normalmente, la complejidad temporal de un algoritmo depende de los datos de entrada. Esto puede depender tanto del tamaño de los datos de origen como de su volumen. Si denotamos el valor del parámetro de complejidad temporal α del algoritmo con el símbolo Tα, y la letra V denota algún parámetro numérico que caracteriza los datos originales, entonces la complejidad temporal se puede representar como una función Tα(V). La elección del parámetro V depende del problema a resolver o del tipo de algoritmo utilizado para resolverlo.

Ejemplo 1. Estimemos la complejidad temporal del algoritmo para calcular el factorial de un número entero positivo.

Función Factorial(x:Entero): Entero;

Var m,i: Entero;

Para i:=2 A x Do m:=ro*i;

Contemos el número total de operaciones realizadas por el programa para un valor dado de x. El operador m:=1; se ejecuta una vez. el cuerpo del bucle (en el que se ejecutan dos operaciones: multiplicación y asignación) x - 1 vez; La asignación Factorial:=m se realiza una vez. Si cada una de las operaciones se toma como una unidad de complejidad, entonces la complejidad temporal de todo el algoritmo será 1 + 2 (x - 1) + 1 = 2x Por lo tanto, está claro que el valor x debe tomarse como parámetro. La función de complejidad del tiempo resultó ser la siguiente:

En este caso, podemos decir que la complejidad del tiempo depende linealmente del parámetro de datos: el valor del argumento de la función factorial.

Ejemplo 2. Cálculo del producto escalar de dos vectores A = (a1, a2,…, ak), B = (b1, b2,…, bk).

Para i:=l Para k Hacer AB:=AB+A[i]*B[i];

En este problema, el volumen de datos de entrada es n = 2k. El número de operaciones realizadas es 1 + 3k = 1 + 3(n/2). Aquí puedes tomar V= k= n/2. La complejidad del algoritmo no depende de los valores de los elementos de los vectores A y B. Como en el ejemplo anterior, aquí podemos hablar de una dependencia lineal de la complejidad del tiempo con respecto al parámetro de datos.

Generalmente se asocian dos problemas teóricos con el parámetro de complejidad temporal de un algoritmo. La primera es encontrar una respuesta a la pregunta: ¿hasta qué límite de complejidad temporal se puede llegar mejorando el algoritmo para resolver el problema? Este límite depende del problema en sí y por tanto es una característica propia.

El segundo problema está relacionado con la clasificación de algoritmos por complejidad temporal. La función Tα(V) generalmente crece a medida que aumenta V. ¿A qué velocidad crece? Hay algoritmos con una dependencia lineal de Tα de V (como fue el caso en los ejemplos que consideramos), con una dependencia cuadrática y con una dependencia de grados superiores. Estos algoritmos se denominan polinomiales. Y hay algoritmos cuya complejidad crece más rápido que cualquier polinomio. El problema que los teóricos de algoritmos suelen resolver es la siguiente pregunta: ¿es posible un algoritmo polinomial para un problema determinado?

Funciones que se encuentran a menudo al analizar algoritmos:

• registro norte(tiempo logarítmico),
• norte(tiempo lineal),
• norte registro norte,
• norte 2 (tiempo cuadrático),
• 2norte(tiempo exponencial).

Las primeras cuatro funciones tienen una tasa de crecimiento baja y los algoritmos cuyo tiempo de operación se estima mediante estas funciones pueden considerarse rápidos. La tasa de crecimiento de una función exponencial a veces se caracteriza como "explosiva". A modo de comparación, supongamos que existen algoritmos cuya complejidad (número de operaciones) se refleja con bastante precisión en estas funciones. Dejemos que estos algoritmos se ejecuten en una computadora que funciona a una velocidad de 10 12 operaciones por segundo. Con longitud de entrada norte≤ 100.000 algoritmos cuya velocidad se estima mediante las cuatro primeras funciones recibirán una respuesta en una minúscula fracción de segundo. Para un algoritmo con complejidad 2 norte El tiempo de funcionamiento se estima de la siguiente manera:

• norte= 50 ≈ 19 minutos,
• norte= 60 ≈ 320 horas,
• norte= 70 ≈ 37 años.

Pregunta 15=49. Algoritmos secuenciales, cíclicos y recursivos.

Algoritmos secuenciales – algoritmos en los que los bloques se ejecutan secuencialmente uno tras otro, en el orden de un esquema determinado.

Ejemplo. Calcula el perímetro de un triángulo de lados a,b,c.13

Algoritmo de estructura de ramificación

En la práctica, rara vez es posible presentar la solución a un problema en forma de algoritmo.

estructura lineal. A menudo dependiendo de cualquier intermedio

Los resultados del cálculo se llevan a cabo según uno u otro.

fórmulas, es decir dependiendo del cumplimiento de alguna condición lógica

el proceso computacional se lleva a cabo según una u otra fórmula.

El algoritmo para tal proceso computacional se llama algoritmo.

estructura ramificada.

La ramificación es una estructura de control que organiza la ejecución de sólo

una de las dos acciones indicadas dependiendo de la equidad

alguna condición.

Una condición es una pregunta que tiene dos posibles respuestas: sí o no.

La ramificación se registra de dos formas: completa e incompleta (Fig. 1 a, b).

a) forma completa b) forma incompleta

Algoritmos cíclicos – algoritmos en los que es necesario calcular repetidamente valores utilizando las mismas dependencias matemáticas (diagramas de bloques) para diferentes valores de las cantidades incluidas en ellos. El uso de bucles puede reducir significativamente el tamaño del circuito.

algoritmo y la duración del programa correspondiente. Hay ciclos con

un número determinado y desconocido de repeticiones. Con un número determinado de repeticiones -

bucle con contador. Con un número desconocido de repeticiones: un bucle con una condición previa,

bucle con poscondición.

Una función (o procedimiento) que directa o indirectamente se refiere a sí misma se llama recursiva. La recursividad es un método para definir una función a través de sus valores anteriores y previamente definidos, así como un método

organización de cálculos en los que una función se llama a sí misma con otro argumento

Al implementar algoritmos recursivos, cada paso de recursividad no resuelve directamente el problema, sino que lo reduce al mismo problema de menor tamaño. Este proceso debería resultar en un problema de tal tamaño que

la solución es bastante fácil. Luego, el “movimiento inverso” da soluciones sucesivas para un problema de tamaño cada vez mayor, hasta llegar al original. La implementación de un procedimiento recursivo se basa en una pila (memoria tipo almacén), que almacena los datos involucrados en todas las llamadas al procedimiento en las que aún no ha completado su trabajo. La recursividad es una forma de organizar el proceso de cálculo cuando el algoritmo se refiere a sí mismo. El principio de recursividad le permite resolver un problema complejo resolviendo secuencialmente subproblemas más simples. Como regla general, la recursividad es necesaria en los casos en que es necesario analizar demasiadas opciones. La recursividad se considera una de las variedades de algoritmo cíclico. La forma recursiva de organización permite darle al algoritmo una forma más compacta. Por lo tanto, el problema se resuelve de complejo a simple: el contenido del algoritmo recursivo refleja un objeto más complejo a través de uno más simple del mismo tipo. Normalmente, un algoritmo recursivo contiene las siguientes partes principales:

– condición para completar el ciclo;

– el cuerpo de la recursividad, que incluye acciones destinadas a

ejecución en cada iteración;

– un paso de recursividad en el que el algoritmo recursivo se llama a sí mismo.

Existe una distinción entre recursividad directa e indirecta. En el primer caso, el algoritmo

contiene una función que se llama a sí misma. Si una función llama a otra función, que a su vez llama a la primera, entonces dicha función

se llama indirectamente recursivo.

El principal requisito para los algoritmos recursivos es que el proceso de reversión no sea

debe ser infinito. En otras palabras, debe implementarse

comprobar la finalización de la llamada, o en una definición recursiva debería

existe una restricción bajo la cual una mayor inicialización

la recursividad se detiene.

Un ejemplo de función recursiva es calcular el factorial de un número.

int factoria(int n)

si (n) devuelve n* factoria(n-1);

de lo contrario, devuelve 1;

Ejemplo de un procedimiento recursivo:

procedimiento Rec(a: entero);

comenzar si a>0 entonces Rec(a-1);

escrito(a); La mayoría de las operaciones de un programa se realizan sólo una o pocas veces. Algoritmos de complejidad constante. Cualquier algoritmo que siempre requiera la misma cantidad de tiempo, independientemente del tamaño de los datos, tiene Complejidad constante.

EN) - tiempo de ejecución del programa lineal generalmente cuando cada elemento de los datos de entrada necesita procesarse solo un número lineal de veces.

O(N 2), O(N 3), O(N a) - Complejidad polinomial.

O (N 2) -complejidad cuadrática, O (N 3) -complejidad cúbica

O(Registro(N)) -¿Cuándo dura el programa? logarítmico, el programa comienza a ejecutarse mucho más lento a medida que aumenta N. Este tiempo de ejecución generalmente se encuentra en programas que dividen un problema grande en problemas pequeños y los resuelven por separado.

O(N*log(N)) - Este es el tiempo de operación para aquellos algoritmos que dividir un gran problema en pequeños, y luego, habiéndolos resuelto, combine sus soluciones.

O(2 N) = Complejidad exponencial. Estos algoritmos suelen surgir de un enfoque llamado fuerza bruta.

Un programador debe poder analizar algoritmos y determinar su complejidad. La complejidad temporal de un algoritmo se puede calcular basándose en un análisis de sus estructuras de control.

Los algoritmos sin bucles y llamadas recursivas tienen una complejidad constante. Si no hay recursividad ni bucles, todas las estructuras de control pueden reducirse a estructuras de complejidad constante. En consecuencia, todo el algoritmo también se caracteriza por una complejidad constante.

Determinar la complejidad de un algoritmo se reduce principalmente a analizar bucles y llamadas recursivas.

Por ejemplo, considere un algoritmo para procesar elementos de una matriz.
Para i:=1 a N hacer
Comenzar
...
Fin;

La complejidad de este algoritmo es O(N), porque El cuerpo del bucle se ejecuta N veces y la complejidad del cuerpo del bucle es O (1).

Si un bucle está anidado dentro de otro y ambos bucles dependen del tamaño de la misma variable, entonces todo el diseño se caracteriza por una complejidad cuadrática.
Para i:=1 a N hacer
Para j:=1 a N hacer
Comenzar
...
Fin;
La complejidad de este programa es O(N 2).

Hay Dos formas de analizar la complejidad de un algoritmo: ascendente. (desde las estructuras de control interno hasta las externas) y descendiendo (de externo e interno).

O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(condición dominante)=O(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O (N 2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N 2)= O(N 3);
O(D)=O(A)+O(E)=O(1)+ O(N 3)= O(N 3)

La complejidad de este algoritmo es O(N 3).

Normalmente, alrededor del 90% del tiempo de ejecución de un programa requiere repetición y sólo el 10% consiste en cálculos reales. El análisis de la complejidad de los programas muestra en qué fragmentos se encuentran este 90%: estos son los ciclos de mayor profundidad de anidamiento. Las repeticiones se pueden organizar como bucles anidados o recursividad anidada.

El programador puede utilizar esta información para crear un programa más eficiente de la siguiente manera. En primer lugar, puedes intentar reducir la profundidad de anidamiento de repeticiones. Luego debería considerar reducir la cantidad de declaraciones en los bucles más profundamente anidados. Si el 90% del tiempo de ejecución se dedica a ejecutar bucles internos, entonces una reducción del 30% en estas pequeñas secciones da como resultado una reducción del 90% * 30% = 27% en el tiempo de ejecución de todo el programa.

Este es el ejemplo más simple.

Una rama separada de las matemáticas se ocupa del análisis de la efectividad de los algoritmos, y encontrar la función más óptima no es tan simple.

vamos a evaluar algoritmo para búsqueda binaria en una matriz - dicotomía.

La esencia del algoritmo: vamos al medio de la matriz y buscamos una coincidencia entre la clave y el valor del elemento del medio. Si no podemos encontrar una coincidencia, observamos el tamaño relativo de la clave y el valor del elemento central y luego nos movemos a la mitad inferior o superior de la lista. En esta mitad volvemos a buscar el medio y lo comparamos nuevamente con la clave. Si eso no funciona, vuelva a dividir el intervalo actual por la mitad.

búsqueda de función (baja, alta, clave: entero): entero;
var
medio, datos: entero;
comenzar
mientras está bajo<=high do
comenzar
medio:=(bajo+alto) div 2;
datos:=a;
si clave = datos entonces
búsqueda:=media
demás
si clave< data then
alto: = medio-1
demás
bajo:=medio+1;
fin;
búsqueda:=-1;
fin;

La primera iteración del bucle se ocupa de la lista completa. Cada iteración posterior reduce a la mitad el tamaño de la sublista. Entonces, los tamaños de lista para el algoritmo son

n n/2 1 n/2 2 n/2 3 n/2 4 ... n/2 m

Al final habrá un número entero m tal que

n/2m<2 или n<2 m+1

Dado que m es el primer número entero para el cual n/2 m<2, то должно быть верно

n/2 m-1 >=2 o 2 m =

De esto se desprende que
2 metros = Toma el logaritmo de cada lado de la desigualdad y obtén
m= El valor de m es el mayor entero que =<х.
Entonces O(log 2 n).

Normalmente, el problema a resolver tiene un "tamaño" natural (generalmente la cantidad de datos que procesa) que llamamos N. En última instancia, nos gustaría tener una expresión para el tiempo que le toma al programa procesar datos de tamaño N como un función de N. Normalmente nos interesa el caso promedio: el tiempo de ejecución esperado del programa con datos de entrada "típicos", y el peor de los casos: el tiempo de ejecución esperado del programa con los peores datos de entrada.

Algunos algoritmos se entienden bien en el sentido de que se conocen las fórmulas matemáticas exactas para los casos promedio y peor. Estas fórmulas se desarrollan estudiando cuidadosamente los programas para encontrar el tiempo de ejecución en términos de características matemáticas y luego realizando un análisis matemático de los mismos.

Varias razones importantes para este tipo de análisis:
1. Los programas escritos en un lenguaje de alto nivel se traducen a códigos de máquina y puede resultar difícil comprender cuánto tiempo llevará ejecutar una declaración en particular.
2. Muchos programas son muy sensibles a los datos de entrada y su eficacia puede depender en gran medida de ellos. El caso medio puede resultar una ficción matemática no relacionada con los datos sobre los que se utiliza el programa, y ​​el peor de los casos es poco probable.

Los mejores, promedio y peores casos juegan un papel muy importante en la clasificación.
Cantidad de cálculos al ordenar.

El análisis de complejidad O se ha generalizado en muchas aplicaciones prácticas. Sin embargo, es necesario entender claramente sus limitaciones.

A principales desventajas del enfoque Se pueden incluir los siguientes:
1) para algoritmos complejos, obtener estimaciones O suele ser muy laborioso o prácticamente imposible,
2) a menudo es difícil determinar la dificultad "en promedio",
3) Las puntuaciones O son demasiado generales para reflejar diferencias más sutiles entre algoritmos.
4) El análisis O proporciona muy poca información (o ninguna) para analizar el comportamiento de los algoritmos cuando procesan pequeñas cantidades de datos.

Definir la complejidad en notación O está lejos de ser una tarea trivial. En particular, la eficiencia de la búsqueda binaria no está determinada por la profundidad del anidamiento de los bucles, sino por el método de selección de cada intento sucesivo.

Otra dificultad es definir el “caso promedio”. Esto suele ser bastante difícil de hacer debido a la imposibilidad de predecir las condiciones operativas del algoritmo. A veces se utiliza un algoritmo como un fragmento de un programa grande y complejo. A veces, la eficiencia del hardware y/o del sistema operativo, o de algún componente del compilador, afecta significativamente la complejidad del algoritmo. A menudo, el mismo algoritmo se puede utilizar en muchas aplicaciones diferentes.

Debido a las dificultades asociadas con la realización de un análisis de complejidad de tiempo "promedio" de un algoritmo, a menudo uno tiene que conformarse con estimaciones del peor y del mejor de los casos. Estos puntajes definen esencialmente los límites superior e inferior de la dificultad "promedio". En realidad, si no es posible analizar la complejidad de un algoritmo "en promedio", queda seguir una de las leyes de Murphy, según la cual la estimación obtenida para el peor de los casos puede servir como una buena aproximación de la complejidad "en promedio". .”

Quizás el principal inconveniente de las funciones O sea su excesiva tosquedad. Si el algoritmo A realiza una determinada tarea en 0,001*N s, mientras que el algoritmo B requiere 1000*N s para resolver el mismo problema, entonces B es un millón de veces más rápido que A. Sin embargo, A y B tienen la misma complejidad temporal O( NORTE).

La mayor parte de esta conferencia se dedicó al análisis de la complejidad temporal de los algoritmos. Hay otras formas de complejidad que no deben olvidarse: la complejidad espacial y la intelectual.

La complejidad del espacio como cantidad de memoria necesaria para ejecutar un programa ya se mencionó anteriormente.

El análisis de la complejidad intelectual de un algoritmo examina la comprensibilidad de los algoritmos y la complejidad de su desarrollo.

Las tres formas de complejidad suelen estar interrelacionadas. Normalmente, al desarrollar un algoritmo con una buena estimación de la complejidad temporal, hay que sacrificar su complejidad espacial y/o intelectual. Por ejemplo, el algoritmo de clasificación rápida es significativamente más rápido que el algoritmo de clasificación por selección. El precio por aumentar la velocidad de clasificación se expresa en la mayor cantidad de memoria necesaria para la clasificación. La necesidad de memoria adicional para la clasificación rápida se debe a múltiples llamadas recursivas.

El algoritmo de clasificación rápida también se caracteriza por una mayor complejidad intelectual en comparación con el algoritmo de clasificación por inserción. Si le pide a cien personas que clasifiquen una secuencia de objetos, lo más probable es que la mayoría utilice el algoritmo de clasificación por selección. También es poco probable que alguno de ellos utilice la clasificación rápida. Las razones de la mayor complejidad intelectual y espacial de Quicksort son obvias: el algoritmo es recursivo, es bastante difícil de describir, el algoritmo es más largo (es decir, el texto del programa) que los algoritmos de clasificación más simples.