Bonjour,
J'ai du mal a comprendre pourquoi la complexité de l'algorithme de la question 4 de l'examen de 2015 est en O(t) et non en O(log t) puisque on traite chaque cas deux éléments a la fois.
Merci d'avance.
Bonjour,
Attention à ne pas confondre un algorithme qui traite deux éléments à chaque fois d'un algorithme qui réduit d'une demi le nombre d'éléments à traiter à chaque fois. Sékoi dans son appel récursif va donner une liste de taille (t-2) par rapport à la taille de la liste de base et ce jusqu'à arriver à un t<2. Combien de fois pouvons nous soustraire 2 à t pour arriver à 2 ? (t-1)/2 fois ce qui est O(t).
On aurait une complexité logarithmique dans le cas ou on réduit de moitié la liste donné à l'appel récursif, vu qu'on ne peut diviser t par 2 qu'un nombre log(t) de fois avant d'arriver en dessous de 2.
Attention à ne pas confondre un algorithme qui traite deux éléments à chaque fois d'un algorithme qui réduit d'une demi le nombre d'éléments à traiter à chaque fois. Sékoi dans son appel récursif va donner une liste de taille (t-2) par rapport à la taille de la liste de base et ce jusqu'à arriver à un t<2. Combien de fois pouvons nous soustraire 2 à t pour arriver à 2 ? (t-1)/2 fois ce qui est O(t).
On aurait une complexité logarithmique dans le cas ou on réduit de moitié la liste donné à l'appel récursif, vu qu'on ne peut diviser t par 2 qu'un nombre log(t) de fois avant d'arriver en dessous de 2.