Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

اینجــــا یک کتابخانه دیجیتالی است

با بیش از 100000 منبع الکترونیکی رایگان به زبان فارسی ، عربی و انگلیسی

Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] - نسخه متنی

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

| نمايش فراداده ، افزودن یک نقد و بررسی
افزودن به کتابخانه شخصی
ارسال به دوستان
جستجو در متن کتاب
بیشتر
تنظیمات قلم

فونت

اندازه قلم

+ - پیش فرض

حالت نمایش

روز نیمروز شب
جستجو در لغت نامه
بیشتر
لیست موضوعات
توضیحات
افزودن یادداشت جدید










Chapter outline



Section 30.1 presents two ways to represent polynomials: the coefficient representation and the point-value representation. The straightforward methods for multiplying polynomials -equations (30.1) and (30.2) -take Θ(n2) time when the polynomials are represented in coefficient form, but only Θ(n) time when they are represented in point-value form. We can, however, multiply polynomials using the coefficient representation in only Θ(n lg n) time by converting between the two representations. To see why this works, we must first study complex roots of unity, which we do in Section 30.2. Then, we use the FFT and its inverse, also described in Section 30.2, to perform the conversions. Section 30.3 shows how to implement the FFT quickly in both serial and parallel models.

This chapter uses complex numbers extensively, and the symbol i will be used exclusively to denote .



/ 292