الفصل الثالث

Growth of functions

نمو الدوال

مقدمة

في الفصل التاني اتعرضنا لبعض الalgorithms اللي بتحل مشكلة الsorting واتكلمنا عن الrunning time لكل algorithm ولكن أجلنا الكلام عن ازاي نعبر عن الrunning time باستخدام الnotations , في الفصل ده هنتعلم ازاي نعبر عم الrunning time لاي algorithm بشكل precise(دقيق جدا).

نفهم عنوان الفصل اللي بنتكلم فيه , functions يعني دوال وده لأنه بيستخدم بعض الدوال للتعبير عن الrunning time للalgorithms , بعد تعريف الدوال دي بيستخدمها كnotation بعد كدة على مدار الكتاب , وكلمة growth يعني نمو أو زيادة الدخل , وده لإن أهم حاجة وانت بتمثل الrunning time ان التمثيل ده يكون بيوصف الrunning time صح مهما الinput يزيد , يعني من الاخر هنستخدم بعض الدوال للتعبير عن كفاءة الalgorithm او الrunning time للalgorithm عند زيادة الدخل , وليه عند زيادة الدخل؟ ده لإن أي algorithm ممكن يكون أداءه سريع على input صغير ولكن الalgorithm بتبان مدى كفاءته عند زيادة الدخل لأرقام كبيرة جدا. اتعرضنا في الفصل التاني لمفهوم ال order of growth , وكلمة order لما تيجي وسط الكلام عن الرياضة والمعادلات بتعني أس , ال order of growth هو الأس اللي له أكبر تأثير على الخرج عند زيادة الدخل , وهو طبعا أكبر أس في المعادلة , يعني مثلا لو عندنا المعادلة دي 3n³ + 5n² + 10 وانها معادلة بتوصف الrunning time لalgorithm , طبعا واضح إن أكبر أس في المعادلة هو 3 فهو ده الorder of growth , هو اللي بياثر عند زيادة الدخل بمعنى ان لو الدخل وصل 1000 فقيمة باقي المعادلة(5000010) بتساوي قليل جدا بالنسبة لقيمة الn³ أعلى أس(3000000000) يعني قيمة باقي المعادلة تمثل 0.0017 من قيمة الorder of growth لدرجة يمكن إهمال باقي المعادلة دي عند تمثيل الrunning time.

Asymptotic notation

كلمة asymptotic جاية من كلمة asymptote ومعناها line(خط مستقيم) بيقترب جدا من curve(منحنى) بس عند زيادة الدخل , أما عند الدخل الصغير بيكون بعيد عنه زي مانت شايف في الصورة.

يعني ايه بقى asymptotic notation؟ يعني notation بيقترب جدا من القيمة الحقيقية للrunning time عند زيادة الدخل , ولكن عند دخل صغير بيكون بعيد. وبنفس المعنى asymptotic efficiency يعني الكفاءة عند زيادة الدخل , والasymptotic analysis التحليل عند زيادة الدخل , بيقولك معلومة ان الalgorithm الاكثر كفاءة asymptotically هو أفضل اختيار إلا مع الدخل الصغير, هنعرف باذن الله 5 Asymptotic notations :

1) Big O notation

الO notation هي function بتستخدم لتحديد ال upper bound(الحد الأقصى) لأي function تانية , والحد الأقصى مش بالضرورة يكون حاجة واحدة بس بمعنى ان انا ممكن احدد اكتر من حد لدالة معينة متقدرش تعدي ولا واحد فيهم , يعني كمثال f(n) = 5n² + 11n + 13 الO notation ليها f(n) = O(n²) وده رياضيا معناه ان فيه constant لو ضربته في n² الدالة f(n) متقدرش تعديه لما يكون الدخل أكبر من قيمة معينة بنسميها n₀ , والصورة اللي جاية بتمثل ال O notation .

لما نكتب f(n) = O(n²) أو أي notation تاني احنا بنستخدم ال = بمعنى ينتمي إلى يعني الدالة f(n) بتنتمي للمجموعة(set) المتمثلة بO(n²) أو أي notation زي ماقلنا.

الحد اللي بتعرفه دالة الO فيه منه نوعين : نوع بنسميه asymptotically tight وده معناه ان الحد ده ممكن الدالة تساويه زي المثال اللي فات f(n) = 5n² + 11n + 13 = O(n²)الدالة فيها أس n² والحد الأقصى ليها n² وبالتالي في علاقة تساوي بينهم ممكنة f(n) <= O(n²) , أما النوع التاني هو عكسه not asymptotically tight وده معناه ان الدالة لا يمكن تساوي أو تلامس الحد , كمثال f(n) = 5n² + 11n + 13 = O(n³) الn³ برده حد أقصى لا يمكن الدالة f(n) تعديه ولكنها لا يمكن توصله برده وبالتالي العلاقة بينهم مفهاش تساوي f(n) < O(n³) .

الO notation بنستخدمه في إيه في ال algorithms? بنستخدمه في التعبير عن الWorst-case running time لإن احنا في الworst-case بنحتاج نحدد أقصى (upper) وقت ممكن ياخده الalgorithm في حل المشكلة , كمثال نقدر نعبر عن الworst-case running time للinsertion sort ب T(n) = O(n²) زي ماعرفنا فالفصل التاني.

2) Big Omega notation

الΩ notation هي function بتستخدم لتحديد الlower bound(الحد الأدنى) لأي function تانية , ونفس الكلام فيه اكتر من حد للدالة , نفس المثال f(n) = 5n² + 11n + 13 الΩ notation ليها f(n) = Ω(n) , وبنفس الطريقة ده رياضيا معناه ان في constant لو ضربته في n الدالة f(n) متقدرش تعديه لما يكون الدخل أكبر من قيمة معينة بنسميها n₀ , والصورة اللي جاية بتمثل الΩ notation

وبنفس الطريقة فيه نوعين للbound هما asymptotically tight والتاني not asymptotically tight وتم شرحهم ولكن الفرق ان ال Ω notation بتحدد الحد الادنى فبالتالي العلاقة f(n) >= Ω(n) او f(n) > Ω(n).

ال Ω notation بتستخدم في إيه في ال algorithms? بتستخدم في التعبير عن الbest-case running time لإن احنا في الbest-case بنحتاج نحدد أقل (lower) وقت ممكن ياخده ال algorithm لحل المشكلة , كمثال نقدر نعبر عن الbest-case running time للinsertion sort ب T(n) = Ω(n) زي ماعرفنا فالفصل التاني.

3) Theta notation

ال Θ notation هي عبارة عن مجموع ال O notation وال Ω notation يعني هي دالة بتحدد lower and upper bounds ل function تانية , كمثال f(n) = 15n + 3 ال Θ notation هيكون g(n) = Θ(n) , وفي الحالة دي بنسمي الدالة g(n) انها asymptotically tight bound للدالة f(n) , وده معناه رياضيا ان فيه 2 constants لو ضربتهم في n يمثلو upper and lower bounds للدالة f(n) لما يكون الدخل أكبر من قيمة معينة بنسميها n₀ , والصورة دي بتوضح ال Θ notation

لو قلت ان f(n) = Θ(n) فتقدر تستنتج حاجتين

f(n) = O(n) , f(n) = Ω(n)

والعكس صحيح يعني لو اثبت ال O وال Ω وطلعو نفس الfunction تقدر تستنج ال Θ.

4) Little o notation

الo notation هي بالظبط الO notation بس الbound بتاعها بيكون not asymptotically tight بس ومينفعش يكون asymptotically tight , كمثال

f(n) = 19n³ + 4n² + 8n + 3

f(n) = O(n⁴) , f(n) = O(n³)

f(n) = o(n⁴) , f(n) != o(n³)

يعني الo notation بيحدد upper bound للدالة لكن الدالة لا يمكن توصل للbound ده (not asymptotically tight)

5) Little ω notation

الω notation بالنسبة للΩ notation بالظبط زي مالo notation بالنسبة للO notation , يعني هي بتحدد lower bound برده بس not asymptotically tight , كمثال

f(n) = 10n²

f(n) = Ω(n) , f(n) = Ω(n²)

f(n) = ω(n) , f(n) != ω(n²)