Calcul de complexité d'une fonction récursive avec boucle for
Bonjour je suis nouveau sur ce forum et j'aimerais savoir comment calculer la complexité d'une fonction récursive et notamment la complexité de la fonction cis-dessous qui a en plus une boucle for. Merci de votre aide ^^ (la fonction)
Code:
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
31
32
33
34
35
36
37
38
|
def Recherche(bibli, motARechercher, fenetre, listText, file = '/', fileName = '/', premiereRecurrence = True) :
''' Fonction recursive qui recherche des livres selon un mot'''
if premiereRecurrence == True : # pour ne pas que ça se lance lors de la récursion
for texteACacher in listText :
texteACacher.pack_forget() #efface les précédents résultats affichés par la fonction de recherche si elle a été lancé précedemment
fileCopy = file #on sauvegarde le chemin de départ
fileNameCopy = fileName #on sauvegarde le chemin de départ
for livreOuSousBibli in os.listdir('bibliotheque' + file) :
if os.path.isdir('bibliotheque' + file + livreOuSousBibli): # un sous dossier équivaut à une sous-bibliotheque
file += livreOuSousBibli + '/' # on modifie le lien
fileName += livreOuSousBibli[:-3] + '/' # on modifie le lien (-3 pour enlever le nombre qui correspond à la position
# d'une sous-bibliothèque et qui est à la fin du nom du dossier représentnat la sous-bibli)
Recherche(bibli[livreOuSousBibli[:-3]], motARechercher, fenetre, listText, file = file, fileName = fileName, premiereRecurrence = False) # on lance la récursion pour le faire aussi pour les livres dans la sous-bibli
else :
if livreOuSousBibli != '.DS_Store' : # fichier caché sur mac qui est lu par 'listDir' et qui m'a fait perdre de nombreuses heures pour trouver le problème
f = open('bibliotheque' + file + livreOuSousBibli, 'r') #on ouvre un fichier txt correspondant à un livre
lignes = f.readlines()
ensembleDesMots = " ".join(lignes)
ensembleDesMots = ensembleDesMots.replace('\n', '')
ensembleDesMots = ensembleDesMots.split(' ') # on créer ainsi une liste qui contient tout les mots de tout les livres de la bibliothèques
pasDeuxFois = True
for mot in ensembleDesMots : #pour chaque mot :
if mot == motARechercher and pasDeuxFois == True :
# on vérifie si c'est le mot qu'on souhaite rechercher,( pas deux fois permet que si le même livre contient plusieurs fois le mot à rechercher, il ne s'affiche qu'une fois)
pasDeuxFois = False
textAffiche = Label(fenetre, text = 'bibliotheque' + fileName + livreOuSousBibli[:-4]) #le -4 sert à enlever le .txt du fichier qui représente le livre
textAffiche.pack() #affiche le chemin du livre qui contient le le mot souhaité
listText.append(textAffiche) #stocke les labels affichés pour pouvoir les supprimer par la suite
f.close()
file = fileCopy #on réinitialise pour le prochaiin livre en redonnant le chemin de depart
fileName = fileNameCopy #on réinitialise pour le prochaiin livre en redonnant le chemin de depart |
