1. ¿Qué complejidad tiene el siguiente algoritmo? for (i = 0; i < N; i++) initiallen =…
- User
- ¿Qué complejidad tiene el siguiente algoritmo? for (i = 0; i < N; i++) initial_len = len(N) j = 1 while j < initial_len j *= 2
A) O(n) B) O(n*log n) C) O(n^2) D) Ninguna es correcta
- Assistant
La complejidad del algoritmo proporcionado es:
B)
La razón detrás de esto es que el primer bucle "for" tiene una complejidad lineal , ya que se ejecuta N veces. El segundo bucle "while" tiene una complejidad logarítmica ya que "j" se duplica en cada iteración hasta que supera "initial_len". Dado que el segundo bucle está anidado dentro del primer bucle, la complejidad total es .
- User
¿Podrías darme un ejemplo de algoritmo de complejidad O(n) y otro de complejidad O(n^2)?
- Assistant
Aquí tienes un ejemplo de algoritmo de complejidad lineal . Se trata de encontrar el elemento "0" en una lista desordenada:
lista = [1, 3, 5, 0 ,4, 1, 4] for k in lista if k == 0 print "Encontrado" break end endEl número de pasos es como mucho el tamaño de la lista .
Ahora te presento un ejemplo de algoritmo en donde el número de pasos crece con el cuadrado de la longitud de una lista a ordenar. Se trata del algoritmo de ordenamiento burbuja:
lista = [1, 34, 4, 5, 1, 234, 23, 3, 4, 3, 23] len = length(lista) for i = 1:len-1 for j = 2:len if lista[j-1] > lista[j] tmp = lista[j-1] lista[j-1] = lista[j] lista[j] = tmp end end endAl tener dos bucles imbricados, el algoritmo ejecuta iteraciones. En lenguaje algorítmico tiene una complejidad .
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →