Quelle est la désignation big O Pour deux cycles for

Il est difficile pour moi d'analyser ce fragment de code:


public int example/int[] arr/{
int n = arr.length, total = 0 ;
for /int i=0; i < n; i++/
for /int j=0; j <= i; j++/
total += arr[j];
return total;
}


Ces deux boucles n'ont pas de crochets bouclés. Je ne pouvais pas analyser leur difficulté temporaire.
J'ai besoin d'aide pour compter le temps de fonctionnement pour les deux.
Invité:

Babette

Confirmation de:

il
O/n
<sup>
2
</sup>
/

, Puisqu'il y a deux couches de boucles. Le fait qu'il n'y ait pas de supports frisés n'a pas d'importance.

Le cycle externe est effectué
O/n/

Une fois et le cycle interne est effectué d'abord une fois, puis deux fois, jusqu'à
n

fois. Ceci est une séquence arithmétique de
1

avant que
n

, Où est la différence totale égale
1

. Par conséquent, sa quantité est égale


/1 + n/ * /n/ / 2


=
/n^2 + n/ / 2


=
O/n^2/


Ce code pourrait être réécrit en utilisant des crochets comme suit:


for /int i=0; i < n; i++/ {
for /int j=0; j <= i; j++/ {
total += arr[j];
}
}

Emilie

Confirmation de:

Le premier cycle est exécuté
O/n/

temps.
Le cycle imbriqué est exécuté
O/n/

temps.

Donc en général
O/n^2/

.

Pour répondre aux questions, connectez-vous ou registre