← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

30 第30章 多项式与快速傅里叶变换

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.757Z

ion at the leaves. The full FFT circuit Figure 30.6 depicts the entire circuit for n = 8.

The circuit begins with a bit-reversal permutation of the inputs, followed by lg n stages, each stage consisting of n/2 butterflies executed in parallel. Assuming that each butterfly circuit has constant depth, the full circuit has depth Θ(lg n). The butterfly operations at each level of recursion in the FFT procedure are independent,

and so the circuit performs them in parallel. The figure shows wires running from left to

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter030.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea