convertir une boucle Pour imbriquée en une boucle Pour simple
La technique de fenêtre coulissante est utile pour résoudre des problèmes dans les tableaux ou les chaînes,
en particulier il est considéré comme une technique qui pourrait réduire la complexité de temps de O(n2) à O(N).
Cette technique montre comment une boucle imbriquée dans peu de problèmes peut être convertie en une boucle Pour simple
Il y a deux types de problèmes qui peuvent être résolus en utilisant cette technique
- Longueur de fenêtre k est fixée : la longueur de la fenêtre est fixée et il vous est demandé de rechercher quelque chose dans la fenêtre, tel que la somme maximale de toutes les fenêtres, le nombre maximal ou médian de chaque fenêtre. Habituellement, nous avons besoin de types de variables pour maintenir l’état de la fenêtre. Certaines sont aussi simples qu’un entier ou peuvent être aussi compliquées que des structures de données avancées telles que list, files.
- Deux pointeurs + critères: la taille de la fenêtre n'est pas fixée, il vous est généralement demandé de trouver le sous-tableau qui répond aux critères, par exemple, à partir d'un tableau d'entiers, recherchez le nombre de sous-tableaux dont la somme est égale à une valeur cible.
où on peut appliquer cette technique
Étant donné un tableau d'entiers de taille "n". Notre but est de calculer la somme maximale de ‘k’ consécutives éléments dans le tableau.
arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20} ; K=439
arr[] = {100, 200, 300, 400} ; K=2
700
Nous commençons avec le premier indice et la somme jusqu'au k-ième élément. Nous le faisons pour tous les blocs consécutifs possibles ou groupes de k éléments.
Cette méthode nécessite une boucle pour imbriquée, la boucle pour externe commence par l'élément de départ du bloc de k éléments et la boucle interne ou imbriquée calcule la somme jusqu'au k-ème élément.
la complexité est en O(k*n) car il contient deux boucles imbriquées.
import sys
INT_MIN = -sys.maxsize - 1
def maxSomme(tab, n, k):
max_somme = INT_MIN
for i in range(n - k + 1):
somme_courante = 0
for j in range(k):
somme_courante = somme_courante + tab[i + j]
# Update result if required.
max_somme = max(somme_courante, max_somme)
return max_somme
[a b c d e f g h]
une fenêtre coulissante de taille 3 :
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
Ceci est utile si par exemple vous voulez calculer une moyenne de k éléments adjacents, ou si vous souhaitez créer un ensemble de toutes les paires adjacentes etc.
Applications
- Nous calculons la somme des k premiers éléments en utilisant une boucle et stockant la somme dans la variable max_somme.
- Ensuite, nous allons parcourir le tableau jusqu'à la fin et en même temps garder une trace de la somme maximale.
- Pour obtenir la somme actuelle du bloc de k éléments, il suffit de soustraire le premier élément du bloc précédent et d’ajouter le dernier élément du bloc actuel.
Maintenant, il est évident que la complexité temporelle est linéaire O(n) car nous pouvons voir qu’une seule boucle est exécutée dans notre code.
def SommeMax(tab, n, k):
# n doit etre superieur a k
assert n > k
# calculer la somme de k premiers elements
max_somme = 0
for i in range(k):
max_somme += tab[i]
somme_courante = max_somme
for i in range(k, n):
somme_courante += tab[i]-tab[i-k]
max_somme = max(max_somme, somme_courante)
return max_somme
t = [1, 4, 2, 10, 2, 3, 1, 0, 20]
print(SommeMax(t, len(t), 4))
