كيفية حل التعقيد العودية لـ t (n) = t (n/2) + 2^n بواسطة طريقة التكرار؟

Question

أحاول العثور على الحد الأعلى للإقامة والمنخفض ، والذي ربما يكون O (2^n)

t (n) = 1 لـ n <= 4

أعلم أن العضو العام هو:

t (n) = t (n/2^(i + 1)) + sum from i = 0 to k of 2^(n/2^i)

---

من هنا لا أعرف كيف أتابع ..

Answer 1

هناك بعض المشكلات في تدوينك. يجب أن يكون العضو العام:

T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)

بعد هذه الخطوة ، سمحنا i = log(2, n) - 1, ، لهذا السبب T(n/2^(i+1)) = T(1).

وبالتالي، T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k).

لاحظ أن sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) هو 2^n + 2^(n/2) + 2^(n/4) + ..., ، وهو أصغر من 2^n + 2^(n-1) + 2^(n-2) + .... ومع ذلك ، فإن الأشياء الأخيرة هي 2^(n+1) - 1. لذا فإن الأشياء السابقة شيء بين 2^n و 2^(n+1). لذلك ، و مجموع هو O(2^n).

ثم T(n) = O(2^n).