Complexité d'une fonction donnée

Question

Lorsque j'ai analysé la complexité du segment de code ci-dessous, j'ai trouvé qu'il est O (n/2). Mais en cherchant sur Internet, j'ai découvert que c'est probablement O (n). J'aimerais savoir qui a raison.

void function(int n) { 
    int i = 1, k = 100; 
    while (i < n) { 
     k++; 
     i += 2; 
    } 
} 

Answer 1

O (n/2) = O (0,5 N) = O (n). Voir Wikipedia pour plus à ce sujet.

Si f est O (g), alors il existe un certain c et n tel que pour tout x > n, | f (x) | < = c * | g (x) |. A savoir, à partir de l'entrée n, c * g (x) domine f (x).

Il en résulte que O (n/2) = O (n), parce que,

• Si f (x) = x/2 et g (x) = x, alors on fixe c = 0,5 et n = 0.
• Si f (x) = x et g (x) = x/2, puis nous avons mis c = 2 et n = 0.

Notez qu'il existe une infinité de valeurs pour c et n que vous pouvez utiliser pour le prouver. (Dans ce qui précède, je les ai minimisés, mais ce n'est pas nécessaire.)

Answer 2

Quel est le point de la variable k dans la méthode ci-dessus? Peu importe que la notation big-O parle du comportement dans la limite (comme la valeur de n approche l'infini). En tant que tel, la notation big-O est agnostique pour les facteurs et les constantes d'échelle. Ce qui veut dire, pour une constante "c" et facteur d'échelle "s"

O (f (n)) est équivalente à O (s * f (n) + c)

Dans votre cas f (n) = n, s = 1/2 et c = 0. Alors ...

O (n) = O (n/2)

Answer 3

O (n) est le même que O (n/2)

L'idée de la notation big-O est de comprendre à quelle vitesse un algorithme s'exécutera en lui donnant une plus grande entrée. Ainsi, par exemple, si vous doublez la taille de votre entrée, le programme prendra-t-il deux fois plus de temps ou prendra-t-il 4 fois plus de temps. Puisque n et n/2 se comportent tous deux de la même manière que vous faites varier la valeur de N (c'est-à-dire si vous augmentez N d'un facteur 10, les deux N et N/2 sont identiques).