2009-8 第3問 (5)
X = { xi }, Y = { yi }, Z = { zi }, Z = X + Y とすると、
z0 = x0 ∧ y0
z1 = x1 ∧ y0 ⊕ x0 ∧ y1
z2 = x2 ∧ y0 ⊕ x1 ∧ y1 ⊕ x0 ∧ y2 ⊕ x0 ∧ x1 ∧ y0 ∧ y1
...
のように、任意のiに対してziはx0,...,xi-1とy0,...,yi-1で表せる。
各論理積の計算は並列的に計算可能であり、それぞれの計算コストはO(logN)
排他的論理和の計算コストもO(logN)なので、全体の計算コストはO(logN)
z0 = x0 ∧ y0
z1 = x1 ∧ y0 ⊕ x0 ∧ y1
z2 = x2 ∧ y0 ⊕ x1 ∧ y1 ⊕ x0 ∧ y2 ⊕ x0 ∧ x1 ∧ y0 ∧ y1
...
のように、任意のiに対してziはx0,...,xi-1とy0,...,yi-1で表せる。
各論理積の計算は並列的に計算可能であり、それぞれの計算コストはO(logN)
排他的論理和の計算コストもO(logN)なので、全体の計算コストはO(logN)
スポンサーサイト
