كيف يتم حساب قيمة الابسلون ؟؟

التعريف واضح

for some constant ∈ > 0

يعني اي كمية موجبة ثابتة.

لا نقوم بحسابه وانما تظهر قيمته بعد عملية المقارنه.

ملاحظات:

1. الفكرة مقارنة دالتين : الدالة f مع الدالة n مرفوعة للقوة لوغ a للاساس b

فايهما اكبر هو الحل.

2. يجب عند مقارنة الدالتين ان يكون الفرق polynomial .

معنى ذلك ان ∈ يجب ان يحقق هذه الخاصية والا لن ينفع استخدام هذه النظريه.

3. النظرية لا تغطي كل الحالات. ( راجع الملحوظة 2). بمعنى اخر يجب ان تكون احدى الدالتين اكبر او اصغر من الاخرى بمقدار ثابت موجب.

لمزيد من الايضاح يمكن مراجعة كتاب Thomas H. Cormen والامثلة الموجودة فيه.

بالتوفيق،

شاكرة لك وفقك الله

أنا أعرف النظرية و لكن أحيانا يشكل علي معرفة قيمة الابسلون

مثلا لو كانت

T (n) = T (n/2) + 2^n

f(n) =2^n

n اس لوقارتم 1 للأساس 2 =n^0=1

فتكون f(n) اكبر

لكن كيف اتحقق من قيمة الابسلون حتى اعرف اذا كانت تطبق case3 اولا؟؟

و سأطلع على الكتاب بارك الله فيك

وهنا أمثلة آخرى حتى يتضح سؤالي

T (n) = 2T (n/2)+ n log n

T (n) = 16T (n/4)+ n!

اما اذا كانت قيمة f(n)

تساوي n مرفوعه لأي عدد فمن السهل ايجاد قيمة الابسلون منها

بالتعويض عن ابسلون باي قيمة اكبر من الصفر سنجد دائما ان :

2 مرفوع للقوة n اكبر من الداله n مرفوعة للقوة لوغ (1+∈ ) للاساس 2 .

معناه الحالة الثالثة ستتحقق.

طبعا الn دائما نفترض انه عدد كبير جدا مثلا مليون.

قد يكون الفرق بين الدالتين دالة وليس ثابت فهذا معناه انه لا يصلح استخدام النظريه للحل.

يبدو انني قد اخطأت هنا:

الحالة الثالثة غير متحققة في هذا المثال ، لان الفرق بين الدالتين ليس polynomial لسبب بسيط انه لا يمكن حساب قيمة ∈ هنا.