Si a alguien le aparece el siguiente error
NameError: name ‘random’ is not defined
coloquen lo siguiente al inicio del código
import random
😃
Complejidad algorítmica
¿Ya tomaste el Curso de Pensamiento Computacional?
Introducción a la complejidad algorítmica
Abstracción
Notación asintótica
Clases de complejidad algorítmica
Algoritmos de búsqueda y ordenación
Búsqueda lineal
Búsqueda binaria
Ordenamiento de burbuja
Ordenamiento por inserción
Ordenamiento por mezcla
Ambientes virtuales
Ambientes virtuales
Graficado
¿Por qué graficar?
Graficado simple
Algoritmos de optimización
Introducción a la optimización
El problema del morral
Conclusiones
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Aportes 146
Preguntas 25
Si a alguien le aparece el siguiente error
NameError: name ‘random’ is not defined
coloquen lo siguiente al inicio del código
import random
😃
Wowwww, no sabia lo de poner el if en la cadena. Python es lo mejor.
Intente ver que sucedía se si hacia más grande la lista y el rango de números aleatorios.
Lo que me pareció sorprendente fue al abrir top en mi terminal…
Ese programa que parecía tan simple colapso mi sistema, cuando %MEM llega al 87% ya no podía hacer nada y no tenia opción debía desconectar mi Laptop (tengo 8GB de RAM).
Me parece fascinante lo que puede llegar hacer un simple proceso de calculo cuando su input aumenta. En este caso a mayor entrada de input, mayor su consumo de recursos. 😉
Como puedo saber la complejidad algoritmica si reemplazo por esta función?
def busqueda_lineal(lista, objetivo):
return objetivo in lista
Les dejo el código de la clase, buen día
import random
def busqueda_lineal(lista, objetivo):
match = False
for elemento in lista: # O(n)
if elemento == objetivo:
match = True
break
return match
if __name__ == '__main__':
tamano_lista = int(input('De que tamaño sera la lista? : '))
objetivo = int(input('¿Que numeor quieres encontrar?'))
lista = [random.randint(0,100) for i in range(tamano_lista)]
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista ')
Ternarios vs ifs
El operador ternario en python es relativamente reciente, apareció en la versión 2.5 y es el siguiente:
“A” if True else “B”
‘A’“A” if False else “B”
'B’
Es una forma abreviada del if que funciona como expresión (se evalúa y devuelve un valor).
La forma general es:
VALOR1 if CONDICION else VALOR2
Si CONDICION es verdadera, entonces la expresión devuelve VALOR1, si no, devuelve VALOR2.
¿Cuál es el problema del operador ternario?
Sólo se puede usar cuando no te importe no ser compatible con python 2.4. Acordáte que hay (y va a haber hasta el 2013 por lo menos) versiones de Linux en amplio uso con python 2.4
Si ignoramos eso, hay casos en los que simplifica mucho el código. Tomemos el ejemplo de un argumento por default, de un tipo modificable a una función. Ésta es la versión clásica:
class c:
def f(self, arg = None):
if arg is None:
self.arg = []
else:
self.arg = arg
Y esta es la versión “moderna”:
class c:
def f(self, arg = None):
self.arg = 42 if arg is None else arg
¿La ventaja? ¡Se lee de corrido! “self.arg es 42 si arg es None, si no, es arg”
Notas de al sesión 😄
Búsqueda lineal.
if else
directamente en una sola línea de código, para ello la sintaxis es en general (en un f-string) {<operaciones> if <condiciones> else <operaciones>}
.import random
def busqueda_lineal(lista, objetivo):
match = False
for i, elemento in enumerate(lista):
if elemento == objetivo:
match = True
break
return match
if __name__ == '__main__':
tamano_de_lista = int(input('Tamaño de la lista?: '))
objetivo = int(input('Que numero entero quieres encontrar: '))
lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
Alguien sabe por qué la primer línea de código no me funciona? siempre se va a no encontrado así esté en la lista. Ocupé el segundo y me funciona bien.
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
print('El elemento {} {} en la lista'.format(objetivo, "esta" if objetivo else "no esta"))
BUSQUEDA LINEAL
Mejor Caso: Cuando el elemento se encuentra en la primera posición quiere decir que solo realiza 1 iteración el bucle for por lo tanto su complejidad es O(1)
Peor Caso: Cuando el elemento se encuentra en la ultima posición o no se encuentra dentro del array -> O(n)
IMPLEMENTACIÓN DE LA CLASE
import random
# Algoritmo de Busqueda
def linear_search(lista , objetivo):
match = False
# Bucle Principal
for elemento in lista : # O(n) -> Depende del tamaño de la lista
if elemento == objetivo:
match = True
break
return match
if __name__ == "__main__":
t = int(input("Tamanno de Lista: "))
listx = [random.randint(0,100) for i in range(t)]
obj = int(input("Objetivo: "))
print(listx)
encontrado = linear_search(listx , obj)
print(f'El elemento {obj} {"esta" if encontrado else "no esta"} en la lista') # Controlar comillas para no generar ambiguedad
IMPLEMENTACIÓN EN PYTHON
def linear_search(ltx,srch):
for i in range(len(ltx)-1):
if (srch == ltx[i]):
return i
return -1
lista = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
res0 = linear_search(lista,1)
print(res0) # 0
IMPLEMENTACIÓN EN C++
#include <iostream>
using namespace std;
int search(int arr[], int n, int x) {
int i ;
for (i = 0; i < n; i++)
if (arr[i] == x) return i ;
return -1 ;
}
int main(){
int arr[] = { 2, 3, 4, 10, 40 } ;
int x = 10 ;
int n = sizeof(arr) / sizeof(arr[0]) ;
int result = search(arr, n, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
Alguien más tuvo que escribir import random al principio del código? No me reconocía random al principio
Tambien se puede hacer ese ejemplo con un while
y la propiedad iter()
y next()
. Algo asi:
falg = true
values = iter(dic)
while flag:
if obj == next(values):
flag = false
Es un algoritmo de complejodad Lineal O(n). Por lo que su peor, PEOR, caso seria lim n=∞
Daniel Aroesti: define que tipo de clase de big o notation es
Yo en la clase titulada Búsqueda lineal: no lo c tu dime XD
Código
Ejecución
El peor caso es que el valor buscado se encuentre al final de la lista 😦
cuando ejecuto el código, siempre me arroja que el elemento no está en la lista
es un algoritmo O(n), ya que es un solo loop…o asi entendi de la anterior clase. y por ese motivo tambien es busqueda lineal dato por dato
Muy interesante la clase y muy practico el tema de los operadores ternarios
La búsqueda lineal es un algoritmo muy sencillo. Consta en buscar si un elemento se encuentra dentro de una lista, array o un sistema ordenado o no ordenado para poder determinar si el elemento se encuentra en el o forma parte de el.
¿Cuál es el peor caso del siguiente código? Si nos fijamos existe un for loop que crece según el tamaño de la lista, por lo cual nuestro Big O es O(n).
Complejidad de la busqueda lineal = O(n)
agregando sorted al inicio logro ordenar la lista
lista =** sorted**([random.randint(0, 100) for i in range(tamaño_de_lista)])
Búsqueda Lineal
Busca la coincidencia en todos los elementos de manera secuencial (1 a 1).
Su complejidad es lineal O(n)
Notas
<expresion1>if<condicion>else<expresion2>
No sé que disfruto más: las clases en sí o la investigación de las mismas.
PYHTON
LUA
ERLANG
🦾(╬▔皿▔)╯Mi aporte, agregue un try para mostrar tanto el numero objetivo que estamos buscando como la posición en que se encuentra.
el except maneja el error en caso de no encontrarlo.
import random # Importa la libreria random para usar la funcion randint
def busqueda_lineal(lista, objetivo):
match = False
for elemento in lista:# O(n) Es una busqueda lineal.
if elemento == objetivo:
match = True
break # Una vez que encuentra el objetivo se detiene.
return match
def main():
list_size = int(input('¿Qué tamaño tendra la lista?:\n'))
objetivo = int(input('¿Qué número quieres encontrar?:\n'))
lista = [random.randint(0,100)for i in range(list_size)] # Genera lista aleatoria de numeros enteros de tamaño list_size
encontrado = busqueda_lineal(lista, objetivo) # Ejecuta la funcion busqueda_lineal
print(f'{"═" * 80}\n')# Imprime 80 caracteres para separacion.
print(lista,'\n')
try:# Evalua si existe el numero dentro de la lista y lo imprime junto con su pocision.
print(f'{"═" * 80}\n')
print(f'El número {objetivo} esta en la posición {lista.index(objetivo)}\n')
except ValueError:# Muestra mensaje en caso de no encontrarlo.
print(f'{"═" * 80}\n')
print(f'El número {objetivo} no esta en la lista\n')
print(f'{"═" * 80}\n')
if __name__ == '__main__':
main()
Hola a todos, hice un miniprograma aplicando lo que aprendi aqui, la complejidad de mi algoritmo es O(n). Este es el codigo:
<word = input('please introduce a word: ') #complejidad O(n)
found = False
while found == False:
letter = input('now write a letter: ')
print(f'{"congrats letter is in word" if letter in word else "sorry, letter not in worrd try again"}')
if letter in word:
break>
Mi implementacion.
Super ya he aprendido mejor a identificar complex algorithm, quiere decir que el curso esta bueno.
Búsqueda lineal.
Peor de los casos O(n)
Mejor de los casos O(1)
Caso promedio O(n)
Dentro de nuestra complejidad algoritmica, es importante tener en cuenta que el break, solo daría un mejor resultado en un caso promedio.
Vaya! esto si lo entendi!
Alguien puede recomendar un libro para revisar a mayor profundidad sobre complejidad algorítmica?
Se que fue un algoritmo sencillo, pero fue genial haber acertado en el tipo de complejidad haha
Muy buena clase.
Algo importante para recalcar es que si queremos generar una lista con un tamaño por ejemplo de 100 con random.randint van a haber números repetidos lo cual en muchos casos no es lo que se busca. Una alternativa para generar una lista sin números que se repitan sería usar:
lista_numeros = list(range(100))
random.shuffle(lista_numeros)
Les dejo dos ejemplos del algoritmo de búsqueda lineal:
import random
import time
objective = int(input('enter an integer to search:'))
numbers = []
iteration = 0
start = time.time()
numbers = list(range(10))
random.shuffle(numbers)
for j in numbers:
iteration += 1
if j == objective:
final = time.time()
finaltime = final - start
print(f'number {objective} found in {iteration} iterations in {finaltime} seconds')
break
elif objective not in numbers:
print(f'number {objective} not found in generated list')
break
final = time.time()
finaltime = final - start
print(iteration)
print(numbers)
print(finaltime)
Y el de la clase:
import random
def linear_search(list_size, objective):
iteration = 0
match = False
numbers = list(range(list_size))
random.shuffle(numbers)
print(numbers)
for j in numbers:
iteration += 1
if j == objective:
match = True
break
return match and print(f'{iteration} iterations')
if __name__ == "__main__":
list_size = int(input('enter the size of the list: '))
objective = int(input('enter the number to search: '))
search = linear_search(list_size, objective)
print(f'The number {objective} {"is" if search else "is not"} on the list')
Sirmpre nos debemos fijar en el peor de los casos a la hora de analizar su complejidad algoritimica, como era un for que crecia a medida que la lista era grande entonces conclui que la complejidad es lineal O(n)
Le agregué al programa que nos regrese, en caso de que encuentre el elemento, la posición en donde lo encontró en el arreglo:
import random
def busqueda_lineal(lista,objetivo):
match = False
i=0
for elemento in lista: #Complejidad O(n)
if elemento == objetivo:
match = True
break
i += 1
return match,i
if __name__ == '__main__':
tamanio_lista = int(input('De que tamaño sera la lista?: '))
objetivo = int(input('Introduzca el numero a buscar: '))
lista = [random.randint(0,100) for i in range(tamanio_lista)]
encontrado = busqueda_lineal(lista,objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado[0] else "no esta"} en la lista')
if encontrado[0]:
print(f'Posicion: lista[{encontrado[1]}]')
liinial
lineal
Excelente.
O(n)
import random
def busqueda_lineal(lista, objetivo):
match =False
for elemento in lista:
if elemento==objetivo:
match=True
break
return match
if __name__ == "__main__":
tamano_de_lista= int (input('De que tamano sera la lista \n'))
objetivo = int(input('Que numero quieres encontrar \n'))
lista= [random.randint(0,100) for i in range (tamano_de_lista)]
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
import random
def busqueda_lineal(lista, objetivo):
match = False
for elemento in lista:
if elemento == objetivo:
match = True
break
return match
if __name__ == '__main__':
tamano_de_lista = int(input('De que tamano sera la lista?'))
objetivo = int(input('que numero quieres encontrar?'))
lista = [random.randint(0,100) for i in range(tamano_de_lista)
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista ')
# ¿Por que me ocurre esto?
# encontrado = busqueda_lineal(lista, objetivo)
# ^
#SyntaxError: invalid syntax
Adjunto el código de la clase:
import random
def lineal_search(search_list, objective):
"""
apply lineal search in a list (search_list) to find the "objective".
:return: bool
"""
match = False
for element in search_list:
if element == objective:
match = True
break
return match
if __name__ == '__main__':
len_of_list = int(input('what is the len of the list?'))
objective = int(input('which number do you want to find?'))
search_list = [random.randint(0, 100) for i in range(len_of_list)]
finded = lineal_search(search_list, objective)
print(search_list)
print(f'the element {objective} {"is" if finded else "is not"} in '
f'the list')
Me rompe un poco la cabeza que ‘encontrado’ lo definas con la función de búsqueda lineal.
Creo que son mañas de computer scientists
es matematico
Esta es otra opciòn
La complejidad algorítmica es de O(n)
Si es un poquito confuso asimilar las clases con las operaciones, buscare mas información.
import random
def busqueda_lineal(lista, objetivo):
match = False
for elemento in lista:
if elemento == objetivo:
match = True
break
return match
if __name__ == '__main__':
tamano_de_lista = int(input('¿De que tamaño sera la lista? '))
objetivo = int(input('¿Que numero desea encontrar? '))
lista = [random.randint(0,100) for i in range(tamano_de_lista)]
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "No esta"} en la lista')```
si la lista es muy extensa, se vuelve ineficiente
bueno tuve una pequeña odisea de 1 semana (jaja) por este programa, resulta que queria actualizar mi python porque no corría el programa… y termine actualizando mi sistema operativo (debian 10). En fin, si no te corre el script actualizate a python 3.7.
La otra es que se dejo sin responder cual era el peor caso para este algoritmo, y el peor de los casos es cuando el objeto a buscar se encuentre al final de la lista.
si no entienden operadores ternarios, pueden usar esto:
if linear_search(array = list1, target = target) == True:
print("element was found")
else:
print("element not found")
Saben por qué el codigo siempre me devuelve que el número no está? Versión 3.8, el codigo tal cual la clase
Grande Teacher, David Aroesti, de los mejores profesores a mi parecer.
Búsqueda lineal y examinación exhaustiva (del curso anterior) son lo mismo?
Busqueda lineal = crecimiento lineal
Otra manera de afrontar el problmea, solo que en este caso devolvemos el indice del item cuando lo encontramos o -1 si no lo encontramos.
# lineal or O(n)
def find_element_index_in_unsorted_list(list,element):
"""Given a list and an element from the list returns its position
Parameters:
list (list<?>): a sorted list of values
element (?): whatever element existent in the list
Returns:
int: the position in the list or -1 if the item does not exist in the list"""
index = 0
while list[index] != element:
index += 1
if list[index] == element:
return index
return -1
yo pensé que era O(log n)
Acá mi aporte que según lo que creo es un poco mas entendible
import random
def busqueda_lineal(lista, objetivo):
'''
O(n)
int lista = []
int objetivo
match = False
if objetivo in lista:
match = True
return match
'''
match = False
for elemento in lista: # 0(n)
if elemento == objetivo:
match = True
break
return match
def main():
tamano_lista = int(input('Tamano paraobjeto la lista: '))
objetivo = int(input('Objetivo a encontrar: '))
lista = [random.randint(0, 100) for i in range(tamano_lista)]
busqueda_lineal(lista, objetivo)
print(lista)
if objetivo in lista:
print(f'El elemento {objetivo} esta en la lista')
else:
print(f'El elemento {objetivo} no esta en la lista')
#print(f'el elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
if __name__ == '__main__':
main()
Interesante, esa es la razon por la cual implementar metodos de ordenamiento como el burbuja es ineficiente, dada necesidad de tener que recorrer todo el dataset en busqueda del valor.
Genial lo de los operadores ternarios.
Si no logras entender el codigo puedes usar esta version simplificada:
def linear_search(array, aim):
match = False
for i in range(0, len(array)):
if i == aim:
match = True
return match
else:
return match
if linear_search(array = [1, 23, 43, 4, 5, 0, 634, 2 ,34, 12, 3, 4], aim = 0) == True:
print("Element found in the given array!")
else:
print("Element wasn't found in the given array")
Esta es la misma versión pero en vez de usar el array dado toma el input del usuario y lo convierte en una lista para que pueda ser manipulado (incluye comentarios):
#Program for writing a list of numbers, converting them to ints and finding a target
#Linear Search
#Array of numbers
#User is asked to input a series of numbers followed by "," ex: 1,2,3,4,5,6
values = input("Input some comma seprated numbers in which you want to find the target: ")
arr1 = values.split(",") #The values are splited by commas and there they are stored in an array list as strs
print(arr1) #arr1 is printed to see our input
#our target is the number we wanna find in our list, and is converted into an int
target = int(input("What's the number you are searching for?: "))
#str_to_int(arr1) converts the arr1 string elements (that are in strs) into ints
def str_to_int(arr1):
for i in range(0, len(arr1)): #for every index in the range of 0 to the total length of the array
arr1[i] = int(arr1[i]) #It will take that indexes of each values in the array and convert them into ints
return arr1 #Returns the new value of arr1
#This is the linear search function. Recieves as argument the arr1 list and the target
def linear_search(int_arr1, target1):
#Calls the str_to_int(arr1) function
str_to_int(arr1)
global i #i is defines as global to be able to be called at the end
for i in range(0, len(arr1)): #For the i in the range of the total length of the int_arr1
if i == target: #Will compare if the i is a target
return True #If the above order is true, returns that the target was found
else: #If nothing is found
return False #Returns false
#If the linear_search found the target
if linear_search(int_arr1 = arr1, target1 = target) == True:
print(f"{target} is in {i} position") #It will print the position of the target
else: #Otherwise = not found (False)
print(f"{target} wasn't found") #Print that the target wasn't found
Good class!!
5:39 list comprehension
Esta línea no entiendo:
lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
Muchos al igual que yo, se preguntaron si es probable que se repitan los números generados al azar.
La respuesta es sí mis compañeros; y tampoco hay un método específico para generar una lista sin repeticiones ( al menos en Python, si alguien conoce el método en otro lenguaje seria genial si lo puede compartir)
En esos casos, cuando queremos una lista sin duplicidad de los datos(números) vamos a tener que trabajarlo “manualmente” 😦
Una técnica es ir almacenando en una lista los números ya generados, y cada vez que generas uno nuevo verificas si ya estaba en esa lista, lo que significa que está repetido. En ese caso lo rechazas y pasas a obtener otro número random hasta que finalmente se encuentre uno que no esté repetido.
import random
def lista_sin_repeticiones(tamaño,limite):
i = 0
lista_sin_repeticiones = []
for i in range(tamaño):
numero_azar = random.randint(0,limite)
while numero_azar in lista_sin_repeticiones: #!mientras que ese numero al azar ya se encuentre en la lista generada
numero_azar = random.randint(0,limite) #!...entonces genero otro numero
else:
lista_sin_repeticiones.append(numero_azar)
i = i + 1
return lista_sin_repeticiones
if __name__ == "__main__":
tamaño_lista = int(input("Cuál es el tamaño de la lista? "))
limite = int(input("Ingrese el limite para el rango de numeros generados al azar "))
lista_con_repeticiones = [random.randint(0,limite) for i in range(tamaño_lista)]
print(f'lista con repeticiones: {lista_con_repeticiones}')
lista_final = lista_sin_repeticiones(tamaño_lista,limite)
print(f'lista sin repeticiones: {lista_final}')
Tener en cuenta que tanto el range que se utilice para los elementos generados al azar como el lenght de la lista juegan un papel crucial para determinar si la solución es viable.
Como pueden observar en la última ejecución, entré en un loop infinito ya que mi límite para generar valores es desde 0 hasta 8 inclusive ==> [0,8] y estoy exigiendo que la lista sea de un lenght de 10; por lo tango nunca voy a llegar a obtener una lista final ya que utilicé todos los valores posibles (9 en total)
Espero que a alguien le sea útil 😃
Y si consideran que podria mejorarse el código o tienen otras técnicas por favor sean libres de compartir, todos estamos aprendiendo 😄
Saludos!
e aparece error de sintanxis en la palabra esta
Hola a todos, comparto con ustedes el código que realicé en Jupyter Notebook para esta clase. Notarán que hice una variación en el ciclo for para que elcódigo indique la posición del primer objetivo que encontró en la lista aleatoria. Saludos
import random
def busqueda_lineal(lista, objetivo):
match = False
for elemento in lista: #loop depende de un input 0(n)
if elemento == objetivo:
match = True
break
return match
if __name__=="__main__":
tamano_de_lista = int(input("¿De que tamaño sera la lista?: "))
objetivo = int(input("¿Que numero quieres encontrar?: "))
lista = [random.randint(0,10000) for i in range(tamano_de_lista)] #Generar una lista del tamaño de la lista, llena de numeros aleatorios
encontrado = busqueda_lineal(lista,objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista') #Operadores ternarios, podemos genera un if else en una misma linea de codigo
Los operadores ternarios, son lo que pueden generar statements, en una sola líena de código.
El entry point, es bien necesario, debido a que define varias cosas: primera de ellas, es el comienzo de ejecución, es decir, dónde tendremos nuestro inicio del script, en caso de que ese archivo en específico se ejecute directamente. Segundo: Porque podemos necesitar importar algo del archivo. Si queremos traer orden a nuestro código, vamos a necesitar definir, en dónde tendremos el código reutilizable, y en dónde llamamos ese código reutilizable. Por lo que en pocas palabras, necesitamos un entry point.
Comparto mi codigo con algo menos de lineas en la funcion y una forma mas optimizada de importar un modulo
from random import randint
def busqueda_lineal(lista, objetivo):
for elemento in lista:
if elemento == objetivo:
return True
return False
if __name__ == '__main__':
tamano_lista = int(input('De que tamaño sera la lista? '))
objetivo = int(input('Que numero deseas encontrar? '))
lista = [randint(0, 100) for i in range(tamano_lista)]
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
Es interesante saber este tipo de cosas que realmente para los que no tengan mayor conocimiento pueden ser innecesarias pero resulta que al a final no es solamente escribir codigo y ya, sino encontrar la solucion mas factible al problema para la optimizacion de recursos tiempo y calidad del producto, piensen en esto como si alguna App que usen en su nueva actualizacion coloquen un mensaje de “Optimizacion de rendimiento”. Allio es donde realmente se aplica esto.
La búsqueda lineal, es sencilla. Solo tenemos que recorrer un arreglo (ordenado o no), tratando de encontrar un elemento.
Como computer scientist, tienes que entender la computación, y las divergencias que surgen apartir de todos los conceptos, básicos. Sin embargo, es desde los conocimientos más básicos, que podemos solucionar problemas más complejos.
Entender, cómo dar solución a nuestros problemas, con algoritmos conocidos, o basados en estos, es una habilidad que requiere un computer scientist.
¿Y si hago esto?
tamaño_de_la_lista = int(input('tamaño de la lista:'))
objetivo = int(input('que numero quieres encontrar? '))
lista = [ random.randint(0, 100) for i in range(tamaño_de_la_lista) ]
if objetivo in lista:
print(f"El elemento {objetivo} esta en la lista")
else:
print('El elemento no esta en la lista')
Qué Bien!!! Vamos!!😁
Lineal
la complejidad algoritmica es 0(n)
me cuesta a ratos, pero creo que entendí el concepto
numeros random:
Usar librería random
random.ranint(0,100)
Funciones ternarias:
{<statement> if <condition> else <statement>}
Búsqueda lineal:
import random
def linealSearch(list, obj):
i = 0
while i < len(list):
if list[i] == obj:
return i
i += 1
return -1
n = int(input("lenght list: "))
o = int(input("objective: "))
l = [random.randint(0, 50) for i in range(n)]
finded = linealSearch(l, o)
print(l)
if finded != -1:
print(str(o) + " is finded in posc " + str(finded))
else:
print(str(o) + " is not finded")
Ya voy aprendiendo a reconocer el tipo de complejidad de los algoritmos; este ejemplo fue muy ilustrativo. Gracias David.
Me toco buscar en una lista de mil, para que mi numero lo encontraran en la lista.
Si es un tema super interesante, poder revisar para cada algoritmo en que complejidad se mueve.
Hice este pequeño juego basado en la practica de esta clase
import random
import os
puntos = 0
def busquedaLineal(lista, objetivo):
global puntos
if objetivo in lista:
os.system("cls")
print(f"Se encontro el numero {objetivo} en la lista:")
print(lista)
puntos += 1
print(f"su puntuacion es: {puntos}")
else:
os.system("cls")
print(f"No encontramos el numero {objetivo} en la lista:")
print(lista)
print(f"su puntuacion sigue siendo {puntos}")
print("intente con otro numero")
while True:
lista1 = [random.randint(0, 20) for i in range(10)]
try:
os.system("cls")
print("escribe un numero del 0 al 20")
print("si tu numero se encuentra en la lista random ganas")
n = input("")
n = int(n)
n_type = type(n)
if n <= 20:
busquedaLineal(lista1, n)
print("desea volver a jugar? escriba SI o NO")
condition = input("")
if condition.lower() == "si":
pass
elif condition.lower() == "no":
os.system("cls")
print("graciaspor jugar")
print(f"su puntuacion maxima fue {puntos}")
break
else:
os.system("cls")
print("no es una respuesta valida")
break
else:
os.system("cls")
print("no colocaste un valor valido para jugar")
break
except ValueError as e:
os.system("clss")
print("no colocaste un numero")
break
Respondiendo a la pregunta que hizo el profesor cuál es el peor caso de una búsqueda Lineal ? Mi respuesta es:
El peor caso es que encontremos el valor en la última posición de una lista , o en último lugar.
Entendido
import random
def busqueda_lineal(lista, objetivo):
match = False
for elemento in lista: # O(n)
if elemento == objetivo:
match = True
break
return match
def run():
tamano_de_lista = int(input('Indique el tamaño de la lista: '))
objetivo = int(input('Que numero quiere buscar: '))
lista = [random.randint(0,100) for i in range(tamano_de_lista)]
print(lista)
encontrado = busqueda_lineal(lista, objetivo)
print(f'El numero {objetivo} {"esta" if encontrado else "no esta"} en la lista.')
if __name__ == "__main__":
run()
0(n)
import random
def busqueda_lineal(lista , objetivo):
match = False
for elemento in lista: #O(n)
if elemento == objetivo:
match = True
break
return match
if __name__ == "__main__":
tamano_lista = int(input("Cual es el tamaño de la lista: "))
objetivo = int(input("Cual el es numero a buscar? "))
lista = [random.randint(0, 100) for i in range(tamano_lista)]
encontrado = busqueda_lineal(lista, objetivo)
print(lista)
print(f"El numero {objetivo} {'Esta en la lista ' if encontrado else 'No esta en la lista'} ")```
Muy bien explicado!
Excelente clase…!
Muy buena clase.
Estoy tan feliz de haber acertado al final nejndxujsd
Este capítulo responde lo siguiente:
¿En qué consiste la búsqueda lineal?
¿Cuál es la relación de la búsqueda lineal y la complejidad algorítmica?
2 Cosas:
Aquí dejo mi código. Incluyo un contador para registrar el número de ejecuciones…
import random
def busqueda_lineal(lista,objetivo,contador):
for item in lista:
contador+=1
if objetivo==item:
return (True, contador)
continue
return(False,contador)
if __name__=='__main__':
tamano_lista = int(input('Ingrese por favor el tamaño de la lista: '))
objetivo = int(input('Ingrese por favor el objetivo: '))
lista = [random.randint(0,100) for i in range(0,tamano_lista)]
encontrado = busqueda_lineal(lista,objetivo,contador=0)
print(lista)
print(f'El número {objetivo} {"si fue" if encontrado else "no fue"} encontrado')
print(f'La ejecución se realizó {encontrado[1]} veces')
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?