Если 2 вектора a = [a1, a2, ... , an] и b = [b1, b2, ... , bn], то
Точечный продукт задается как a.b = a1 * b1 + a2 * b2 + ... + an * bn
Чтобы вычислить это, мы должны выполнить n умножений и (n-1) сложений. (Я предполагаю, что это алгоритм точечного произведения, на который вы ссылаетесь).
Предполагая, что умножение и сложение являются операциями постоянного времени,
следовательно, сложность времени составляет O(n) + O(n) = O(n).
Единственное вспомогательное пространство, которое нам требуется во время вычисления, - это удержание «частичного точечного произведения на данный момент» и последнего вычисленного произведения, то есть ai * bi.
Предполагая, что мы можем хранить оба значения в постоянном пространстве,
поэтому сложность пространства составляет O(1) + O(1) = O(1).