التحليل الكلي لسلسلة من ن العمليات

Question

أحاول العثور على التكلفة المطفأة لكل عملية في سلسلة من n العمليات على بنية البيانات التي ith تكاليف التشغيل i إذا i هي قوة دقيقة من 2 ، و 1 خلاف ذلك.

أعتقد أنني بحاجة إلى إيجاد طريقة للتعبير عن مجموع التكاليف حتى رقم n, ، ولكن أنا عالقة.أستطيع أن أرى أن خاص ، وأكثر تكلفة i القيم التي تحدث الأب وأبعد عن بعضها البعض:

أنا = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...

لذلك ، يبدو أنه ليس لدي أرقام بين القوى الأولى والثانية من 2 ، ثم رقم واحد ، ثم 3 ، ثم 7.عندما نظرت إلى هذا في حين ، وأنا (تصحيح لي إذا كان هذا هو خارج) وجدت أن عدد غير القوى من 2 بين jth و kth صلاحيات 2 هو 2^(j-1) - 1.

ولكن كيف يمكنني ربط كل هذا معا في خلاصة?أستطيع أن أرى نوعا من شيء على js جنبا إلى جنب مع عدد من القوى الفعلية من 2 أنفسهم ، ولكن أواجه مشكلة توحيد كل ذلك في مفهوم واحد.

Answer 1

لا أستطيع تقديم نموذج مغلق للمجموع، لكن من الواضح أن متوسط تكلفة القمم في صلاحيات اثنين من قيم الذروة المتتالية مقارنة مقارب 3.0، مما يؤدي قبل القوة القادمة إلى الحد الأدنى الذي يرتفع مقاربهنحو 2.0.

كل من القيم (2 ^ n) - 1 بصرامة بين 2 ^ n و 2 ^ (n + 1) يسهم 1 إلى التكلفة الإجمالية (مما تسبب في التأسيس المتوسط لأسفل) حتى القيمة في 2 ^ (n +1) يضيف 2 ^ (n + 1).لذلك متوسط مساهمة القطاع الذي يبدأ بعد 2 ^ n وينتهي ب 2 ^ (n + 1) هو ((2 ^ n) -1 + 2 ^ (n + 1)) / 2 ^ n أو (3 * 2 ^N - 1) / 2 ^ n، الذي يقترب من 3 كما يزيد.

يمكنك أن ترى كلا التأثيرات في الجدول المقنع أدناه.نأمل أن يساعد هذا. giveacodicetagpre.

Answer 2

تتراوح التكلفة المطفأة لكل خطوة من أقل بقليل من 3 (متى ن هي قوة 2) وصولا إلى أقل بقليل من 2 (متى ن هو 1 أقل من قوة 2) ، على النحو التالي.

دع ك (ن) تشير إلى التكلفة الإجمالية لـ ن الخطوات ، والسماح ر (ن) تشير إلى تكلفة قوى 2 التي لا تتجاوز ن.افترض ن = 2^ي.ثم
K(n) = n + T(n) - j
كما يتضح من خلال عزو تكلفة واحدة إلى كل خطوة ، ثم إضافة التكلفة الإجمالية لخطوات قوة 2 ، وطرح ي للاعتماد المزدوج على تلك الخطوات.لأن
T(2^j) = 1 + 2 + 4 +...+ 2^j = 2^(j+1)-1 = 2*n-1,
لدينا
K(n) = 3*n - j - 1,
لتكلفة مطفأة أقل بقليل من 3 متى ن هي قوة 2.

افترض الآن ن = 2^(ي+1) -1.لدينا
K(n) = K(2^j) + n - 2^j
(بسبب ن-2^ي خطوات تكلفة الوحدة بعد الخطوة 2^ي ) ، أي
K(n) = (3*2^j - j - 1) + (2^(j+1) - 1) - 2^j,
أو
K(n) = 2*(2^(j+1)-1) - j = 2*n - j,
لتكلفة مطفأة أقل بقليل من 2 متى ن هو واحد أقل من قوة 2.

Answer 3

التكلفة المطفأة لكل عملية ستكون على الأكثر 3. يمكنك الحصول على هذا إما عن طريق حساب التكلفة الإجمالية لعمليات N وتقسيمها بواسطة N، أو بوسيطة شحن.يمكن بناء حجة الشحن على النحو التالي.

عندما لا أكون قوة 2، تكلف تكلفة الشحن 1.خلاف ذلك عندما أكون من النموذج 2 ^ ك، ستكون تكلفة التشغيل 2 ^ ك، والتي يتم إعادة توزيعها بين العمليات في المراكز: [2 ^ {k-1} +1، 2 ^ k].يمكن القيام بذلك عن طريق زيادة رسوم كل عمليات في [2 ^ {k-1} +1، 2 ^ k-1] المواقع بواسطة 2 وتعيين الرسوم المتبقية 2 إلى العملية في 2 ^ k.بعد إعادة التوزيع، فإن الحد الأقصى لشحن في أي موقف هو 3.

Answer 4

التكلفة الإجمالية للعمليات N -

كيف وصلت إلى هذا -

تكلفة صلاحيات 2 - مجموع صلاحيات N الأولى من 2 هي .منذ أن كنت بحاجة إلى صلاحيات الأرقام حتى n، استبدلت N مع أرضية سجل n.

تكلفة الأرقام الأخرى - سيكون هناك أرقامالمتبقية لها تكلفة وحدة.

أضف كل منهما، وسوف تصل إلى المعادلة.