time-complexity - 变量初始化的触发器计数

Question

考虑以下伪代码：

a <- [0,0,0] （将 3d 向量初始化为零）

b <- [0,0,0] （将 3d 向量初始化为零）

c <- 一个。b（两个向量的点积）

在上面的伪代码中，什么是 flop 计数（即数字浮点运算）？
更一般地说，我想知道的是，在查看算法的复杂性时，变量的初始化是否计入总浮点运算。

Answer 1

在您的情况下，a和b向量都是零，我认为使用零来描述或解释触发器操作不是一个好主意。我会说给定向量 a 具有条目 a1、a2 和 a3，并且还给定向量 b 具有条目 b1、b2、b3。两个向量的点积等于 aTb 给出

aTb = a1*b1+a2*b2+a3*b3

这里我们有 3 个乘法运算 (i.e: a1*b1, a2*b2, a3*b3)和 2 个加法运算。我们总共有 5 次操作或 5 次失败。如果我们想将这个例子推广到 n 维向量 a_n 和 b_n，我们将有 n 次乘法运算和 n 次n-1加法运算。总的来说，我们最终会n+n-1 = 2n-1遇到操作或失败。我希望我上面使用的例子能给你直觉。