Je parcours un ArrayList en utilisant une boucle while et en enlevant les valeurs en place si elles remplissent un certain critère. Mon code est dans l'esprit de l'extrait suivant :
List list = new ArrayList<>();
int N = 1000
// Configuration de la liste pour afficher un exemple
for (int i = 0; i < N; i++) {
list.add(i);
}
Date start = new Date();
// Parcourir toute la liste, en supprimant la moitié des valeurs
Iterator iter = list.iterator();
while (iter.hasNext()) {
Integer in = iter.next();
if (in % 2 == 0) {
// Est-ce pair ?
iter.remove();
}
}
Date end = new Date();
System.out.println(end.getTime() - start.getTime());
System.out.println(list.size());Ce que je veux savoir, c'est si la complexité temporelle de cette boucle d'itération est O(N) ou O(N^2). Je crois qu'il s'agit de O(N^2) car les ArrayList Java sont basés sur un tableau régulier, et pour chaque suppression, vous devez nécessairement déplacer O(N) des valeurs suivantes vers la gauche pour maintenir le tableau dans un état cohérent.
