Complexité algorithmique du code naïf pour traiter toutes les sous-séquences consécutives d'une liste: n ^ 2 ou n ^ 3?

Question

Je suis d'étudier pour un test et trouve cette question:

Je ne peux pas vraiment déterminer la complexité, j'ai compris, c'est soit O(n²) ou O(n³) et je me suis penchée vers O(n³).
Quelqu'un peut-il me dire ce que c'est et pourquoi?

Mon idée qu'il est O(n²) c'est parce que dans l' j boucle, j = i ce qui donne une forme de triangle, puis l' k boucle va de i + 1 de j, ce qui je pense est l'autre moitié de celle du triangle.

public static int what(int[] arr)
{
    int m = arr[0];
    for (int i=0; i<arr.length; i++)
    {
        for (int j=i; j<arr.length;j++)
        {
            int s = arr[i];
            for (int k=i+1; k<=j; k++)
             s += arr[k];
            if (s > m)
             m = s;
        }
    }
    return m;
}

Aussi, si vous pouvez me dire ce qu'il fait?

J'ai pensé qu'il retourne à l'addition de nombres entiers positifs ou le plus grand entier du tableau.
Mais pour les tableaux comme {99, -3, 0, 1} il retourne 99, ce qui, je pense, parce que c'est buggé. Si ce n'est pas que je n'ai aucune Idée de ce qu'il fait:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99 ???

Answer 1

Vous pouvez procéder méthodiquement, à l'aide de Sigma Notation, pour obtenir l'ordre de complexité de croissance:

Answer 2

Vous avez 3 pour les déclarations. Pour les grandes n, il est tout à fait évident, c'est - O(n^3). i et j ont O(n) chaque, k est un peu plus court, mais toujours O(n).

L'algorithme retourne la plus grande somme de termes consécutifs. C'est pourquoi, pour le dernier, il retourne 99, même si vous avez des 0 et des 1, vous avez également -3 qui permettra de déposer votre somme à un maximum de 97.

PS: en forme de Triangle signifie 1 + 2 + ... + n = n(n+1) / 2 = O(n^2)

Answer 3

Code:

 for (int i=0; i<arr.length; i++) // Loop A
{
    for (int j=i; j<arr.length;j++) // Loop B
    {
        for (int k=i+1; k<=j; k++) // Loop C
        {
            // ..
        }
    }
}
 

Analyse asymptotique sur Big-O:

 Loop A: Time = 1 + 1 + 1 + .. 1 (n times) = n

Loop B+C: Time = 1 + 2 + 3 + .. + m = m(m+1)/2

Time = SUM { m(m+1)/2 | m in (n,0] }

Time < n * (n(n+1)/2) = 1/2 n^2 * (n+1) = 1/2 n^3 + 1/2 n^2

Time ~ O(n^3)
 

Answer 4

Peu importe la forme du triangle ou non, c'est toujours une complexité O (N ^ 3), mais bien sûr avec une constante inférieure puis un triple cycle imbriqué complet.

Answer 5

Vous pouvez modéliser le temps d'exécution de la fonction comme

 sum(sum(sum(Theta(1), k=i+1..j),j=i..n),i=1..n)
 

Comme

 sum(sum(sum(1, k=i+1..j),j=i..n),i=1..n) = 1/6 n^3  - 1/6 n,
 

le temps d'exécution est Theta (n ^ 3).