Discussion :

[Alphakiwi]

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 python :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Flodelarab]

Bonjour

La fonction n'est pas récursive puisqu'elle ne s'appelle pas elle-même.

[Alphakiwi]

Si elle s'appelle bien...

la ligne a été mis en rouge dans le code du forum je ne sais pas trop pourquoi ^^

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Flodelarab]

Au temps pour moi. C'est la fonction de recherche de Firefox qui marche toujours aussi mal.

Dans ta situation, on peut appeler f() la fonction numérique donnant la quantité d'opérations nécessaires pour exécuter la fonction recherche(). Tu obtiendras f() en fonction de f(). Soit une formule de récurrence. Tu calculeras alors le terme général de cette suite. C'est la complexité algorithmique de la fonction recherche().