توضيح على FFT.

Question

أعلم أن هناك شيئا خاطئا في التفكير التالي ولكنني لست متأكدا مما هو عليه.

FFT:

1. إعطاء اثنين من متعدد الحدود

   A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n

   و

   B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n

   يمكنك حساب معاملات المنتج

   AB = \sum _k = 0 ^ 2n ( \sum _ j = 0 ^ k (a_j b_{k-j}))x^k

   في O(n log n ) زمن.

2. لذلك نظرا لمتوافرين (a_0, ..., a_n) و (b_0, ..., b_n) يمكننا حساب ناقل v_i = \sum j = 0 ^ k ( a_j b_{k-j}) في O(n log n) الوقت (عن طريق تضمين ناقلات الأصفار.)

3. بالنظر إلى ما سبق، يجب أن نكون قادرين على حساب المنتج نقطة A =(a_0, ..., a_n) و B =(b_0, ..., b_n) الذي A.B = \sum_j=0 ^ n a_j b_j في O(n log n) الوقت من قبل قبل المعالجة واحدة من ناقلات يقول B أن تكون B' = (b_n, b_{n-1}, ..., b_1, b_0) ثم حساب الأزيل كما في 2. في O(n log n) زمن.

إذا كان السبب أعلاه صحيح، فهذا يعني أننا نستطيع تطبيق مصفوفة الضرب لشخصين nxn المصفوفات في O(n^2 log n ) الوقت عن طريق الحوسبة المنتج نقطة في O(n log n) زمن O(n) مرات.

ومع ذلك، فإن أفضل وقت تشغيل لمصفوفة الضرب الذي نعرف عنه O(n^2.4) لذلك يبدو أن هذا غير مرجح أن يكون صحيحا، والذي ربما يعني من الخطوات 1،2، أو 3 غير صحيح.

Answer 1

هناك n^2 إدخالات في المنتج، لا n وهكذا فإن هذه الخوارزمية ستكون O(n^2 * n * log n) = O(n^3 log n).

وأفضل خوارزمية للحوسبة DOT المنتجات O(n), ، ليس O(n log n). وبعد لهذا السبب الخوارزمية السذاجة لضرب المصفوفة O(n^3). وبعد (إنه n^2 منتجات نقطة يمكن القيام بها في O(n) زمن).

Answer 2

أتساءل عن سبب وجود إنجاز في الخطوة 3 يمكنك حساب المنتج النقاط في وقت O (N Log N) لأنه من المعروف جيدا أن منتج DOT يمكن حسابه في وقت O (N)؟ أيضا الخطوة 2 يشبه الوقت الخطي بدلا من خطوة O (N Log N)؟

أيضا الاستنتاج حول O (n ^ 2 سجل n) لا يتبع منطقيا. لا يمكنك أخذ Product Product O (n) مرات مما أدى إلى AB Matrix --- بقدر ما أعرف أن عليك أن تأخذ منتجات DOT O (N ^ 2)، مما يؤدي إلى (لكل تحليلك) O (N ^) 3 سجل ن) وهو أدنى من القياسية O (N ^ 3). هذا بسبب نتيجة المنتج الخاص بك O (N Log N) نتيجة المنتج.