¿Puede la complejidad del tiempo de ejecución de un algoritmo de clasificación basado en comparación ser inferior a N logN?

Los algoritmos de clasificación son los medios para clasificar un conjunto dado de datos en un orden de acuerdo con los requisitos del usuario. Se utilizan principalmente para ordenar datos de manera creciente o decreciente. Hay dos tipos de algoritmos de clasificación: Algoritmos de clasificación basados ​​en comparación Algoritmos de clasificación no basados ​​en la … Continue reading «¿Puede la complejidad del tiempo de ejecución de un algoritmo de clasificación basado en comparación ser inferior a N logN?»

Demostrar que un problema formado por Clique y Conjunto Independiente es NP Completo

Prerrequisito: NP-Completeness , NP Class , Clique , Independent Set Problema: dado un gráfico no dirigido G = (V, E) y un número entero K , determine si existeuna camarilla de tamaño K , así como un conjunto independiente (IS) de tamaño K. Demostrar que es un NP Completo. Explicación: Un Clique es un subgrafo … Continue reading «Demostrar que un problema formado por Clique y Conjunto Independiente es NP Completo»

Demostrar que el subgrafo denso es NP completo por generalización

Prerrequisitos: NP-Completo , Clase NP , Subgrafo denso  Problema : Dada la gráfica G = (V, E) y dos enteros a y b . Un conjunto de varios vértices de G tales que hay al menos b aristas entre ellos se conoce como subgrafo denso delgrafo G. Explicación: Para probar el problema del subgrafo denso … Continue reading «Demostrar que el subgrafo denso es NP completo por generalización»