时间与空间矢量点积计算的复杂
如果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)
。
谢谢。但我需要用n表示。所以时间复杂度将是n +(n-1)和空间2n? – 2010-09-19 01:15:24
big-theta也隐藏常量(在这种情况下,O = big-Theta)。你的意思可能是*等值*。 – 2010-09-19 01:53:13
@Alexandre C:我同意 - 在这种情况下,我提供了Big Theta。是不是暗示(虽然阅读我的评论,这听起来像),只是OP是否意识到这实际上是一个紧张的限制。 – Ani 2010-09-19 02:32:59
你的老师探查是一个点积是一个线性时间'O(N)'操作,其中n是两个向量的长度。这假设你考虑乘法和加法作为恒定时间操作。技术上'*'和'+'不是固定时间。如果要吹毛求疵,并与图灵机的时间复杂度超精密,然后随着数字的平均长度乘以和'了'随着数字的平均长度被添加定义'M'。复杂度变为:'为O(n *(平方公尺1.465)+((N-1)*日志的(a)))',其折叠到:'O(N * M + N *日志的(a))'。 – 2017-03-25 03:03:18