لذلك دعونا نتدرب على فكرة مقارنة اثنين من متعدد الحدود،
على سبيل المثال، وتحديد ما إذا
كانوا ينتمون إلى نفس الفئة أم لا.
لذلك نحدد الطبقة نفسها.
من أجل القيام بذلك، نبدأ مع
فكرة تدوين كبير O،
والتي يشار إليها في بعض الأحيان هو
خط س في النص المكتوب اليد.
الإجراء هنا هو كما يلي.
في الأساس، يفترض أن لدينا اثنين من وظائفنا
كما x مربع و 5X تربيع ناقص 100X.
نحن، بطريقة ما، نتحدث
عن الحد الأعلى
لوظيفة واحدة فيما يتعلق بأخرى.
في الأساس، وهذا يعني أن وظيفة واحدة
أكبر لا يزيد عن عدد ثابت
من المرات من الأخرى.
وبعبارة أخرى، نحن بحاجة إلى كتابة عدم المساواة هنا.
في الأساس، افترض أن لدينا بعض الأحياء
من نقطة معينة، أ، على سبيل المثال.
نسمي وظيفة واحدة
كبيرة O من وظيفة أخرى في هذا الحي.
إذا كان هناك بعض ثابت،
ثابت إيجابي، C مثل العلاقة،
القيمة المطلقة للعلاقة بين
الدالات f و g لا تتجاوز
هذه القيمة c، لذلك دعونا ننظر،
على سبيل المثال، حالتنا.
لدينا x مربع،
على سبيل المثال، دعونا نسميها f هو x مربع،
ز هو 5X مربع ناقص
100x وسأفترض أن x يقترب من اللانهاية.
لذا ما سنفعله، سنقول،
هو أن بعض الوظائف أكبر من
الأخرى في حي ما من اللانهاية.
نحن بحاجة إلى كتابة شيء
مثل القيمة المطلقة لـ f
أقل أو تساوي بعض
الثابت مضروبًا في القيمة المطلقة لـ g، حسنًا؟
وبعبارة أخرى، س تربيع أقل أو أكبر من بعض
ثابت مضروبا في إبسيلون
[غير مسموع] 5X تربيع ناقص 100X.
من السهل جدا أن نفهم ما
هو ثابت هو في الواقع جيدة بالنسبة لنا هنا.
على سبيل المثال، دعونا نبدأ مع
ثابت c، يساوي واحد.
حسنا، من الواضح أنه كذلك،
لأننا إذا افترضنا أن ج يساوي واحد.
وهكذا، نحصل على س مربع على جانب واحد و
5X الساحات ناقص 100X على الجانب الآخر.
إذا طرحنا x تربيع
من كلا الجانبين، وبالتالي، نحصل على وظائف،
والتي هي إيجابية بشكل واضح من نقطة ما،
لأننا نبحث في
وظيفة مكافئ مع إيجابية.
معامل بلدي، وبالتالي،
هناك جذر وبعد هذا الجذر،
لدينا قيم إيجابية فقط.
وهكذا، فإن هذا التفاوت يحمل واحد.
F هو كبير O نحو G،
كان ذلك مثالا واحدا.
يجادل أحد التعليمات البرمجية بسهولة أنه إذا احتجنا
إلى تبديل هذه الوظيفة التي لا تزال قائمة،
فقط لأنه بدلاً من كتابة c يساوي واحد.
دعونا نحاول أن نفعل هذا التفسير هنا.
لذلك أساسا، نحن بحاجة لإثبات شيء، مثل هذا هنا.
لذلك من أجل القيام بكل منها،
نحن بحاجة إلى النظر في شيء آخر c،
صغير واحد، ولكن واحد عظيم.
لذلك أساسا، نبدأ مع مثل ج يساوي خمسة.
ثم نحصل على نتيجة لطيفة هنا.
ولكن هذا ليس هو الحال دائما، لأنه، على سبيل المثال،
دعونا ننظر في بعض الحالات أكثر إثارة للاهتمام.
على سبيل المثال، ما هي الوظائف [غير المسموعة]،
جيب x و x،
حيث يقترب x من الصفر؟ نحن نعرف ماذا؟
إنها في الأساس مكافئات كما ينبغي للمرء أن يتوقعها،
أن الجيب x هو في الأساس كبير O من x،
إنه سهل للغاية، لأن
القيمة المطلقة لشرط x، كما
ذكرنا، بينما كنا نتحدث عن الحد الثاني
المهم، أصبح الآن أكبر من النموذج x،
لأن القيمة المطلقة لـ x
هو في الواقع مساحة القطاع،
وجيب س هو مساحة المثلث على التوالي.
لذلك مع ذلك، نحسب أن
استخدام c ثابت يساوي واحد،
نحصل على هذا الحق تماما.
ولكن ماذا لو استبدلنا نقطة الاهتمام من الصفر،
دعونا نقول ما لا نهاية؟
أولا وقبل كل شيء، الأفكار التي جيب س
هو كبير O نحو x،
لا تزال تحمل في هذه النقطة بالذات، لأنه في الأساس،
شرط س ليست أكبر من واحد و x هو أعظم.
كما يمكنك أن تتخيل، x يقترب من اللانهاية.
وهكذا، فإن هذا التفاوت لا يزال قائما
، على سبيل المثال، لنفس ثابت يساوي واحد.
ولكن إذا قمنا بتغييره،
إذا قمنا بتغيير وظيفتين،
ثم نحصل على 380،
[غير مسموع] هنا، لأن الجيب x
و x لا يرتبط في الأوقات.
لأن شرط x لا يزال، آسف،
لقد قلت لك أننا بحاجة
إلى مبادلة الوظائف ولم نفعل ذلك.
لذلك هو خداع عظيم هنا.
هذا أقل مخادعاً
لذلك x هو كبير O من جيب س
لذلك أساسا، جيب
س يحدها واحد وناقص واحد و x غير محدود.
وهكذا، إذا حاولنا التوصل إلى فكرة
أن x يجب أن يكون أقل من بعض ثابت،
مضروبا في شرط س ونقول أن هذا
الثابت، على سبيل المثال، 10،000.
إذن ما الخطأ؟
ثم يمكننا على سبيل المثال،
واتخاذ x أكبر من اثنين، منذ ن،
هذه المعادلة، ونحن
بالتأكيد تقريبا تسقط فقط
وهذا هو الحال للغاية ليس كذلك.
هذا ليس صحيحاً لذلك عندما
نتحدث عن تدوين Big-O،
تحتاج دائمًا إلى النظر في الأمر هنا.
ما هي الوظيفة، فيما يتعلق بأي وظيفة؟ هل هو كبير أو؟