Complexité en temps et en espace du calcul vectoriel de produit scalaire

Question

Quelle est la complexité temporelle et spatiale d'un algorithme, qui calcule le produit scalaire entre deux vecteurs de longueur n?

Answer 1

Si les 2 vecteurs sont a = [a1, a2, ... , an] et b = [b1, b2, ... , bn], puis

Le produit scalaire est donné par a.b = a1 * b1 + a2 * b2 + ... + an * bn

Pour calculer cela, il faut effectuer n multiplications et (n-1) ajouts. (Je suppose que c'est l'algorithme du produit scalaire auquel vous faites référence). En supposant que la multiplication et l'addition sont des opérations à temps constant, la complexité temporelle est donc O(n) + O(n) = O(n).

Le seul espace auxiliaire dont nous avons besoin au cours du calcul est de maintenir le 'point-produit partiel jusqu'à présent' et le dernier produit calculé, c'est-à-dire ai * bi.

En supposant que nous pouvons maintenir les deux valeurs dans l'espace constant, la complexité de l'espace est donc O(1) + O(1) = O(1).