-
サマリー
あらすじ・解説
شرح الbig O notation
تستخدم فكرة الbig O notation لتحديد الموارد التي تحتاجها الخارزميّات لإتمام عملها. ولهذه الصيغة عدّة أشكال وهي
المدّة الخطّيّة O(n) كلّما زادت المعطيات زادت المدّة المطلوبة لتنفيذ العمليّة
مثالها قراءة معجم من أوّله لآخره، كلّما زادت صفحات الكتاب (المعطيات) زادت المدّة المطلوبة للقراءة.
المدّة الثابته O(1) مهما تغيّرت المعطيات كانت سرعة تنفيذ العمليّة ثابته
مثالها: الذهاب لأوّل صفحة في معجم، مهما زادت صفحاته (المعطيات) لن يؤثّل ذلك على المدّة المطلوبة للتنفيذ
المدّة المتسارعة السلبيّة O(n^2) تتضاعف مدّة التنفيذ كلّما زادت المعطيات بشكل خطّي
مثال: لو أردتّ أن تجد مصطلحات متكرّرة في معجم تستطيع مقارنة كل مصطلح بكل مصطلح آخر في المعجم، فلو كان عندك 10 مصطلحات لقمت ب 100 مقارنة ولو كان عندك 100 مصطلح لقمت بعشرة آلاف مقارنة
المدّة المتسارعة الإيجابيّة O(log n) تزيد مدّة التنفيذ بشكل خطّي كلما تضاعفت المعطيات
مثال: لو طلبت منك البحث عن مصطلح في معجم مرتّب ابجديا تبدأ من نصف المعجم وتنظر إن كان المصطلح المطلوب قبل أو بعد المكان الذي أنت فيه وتترك الجنب الآخر، هذا يقسم مساحة البحث نصف، اعد وكرر على النصف الباقي، ثم الربع الباثي، ثم الثمن الباقي حتّى تصل إلى مكان المصطلح الذي تبحث عنه. كلّما تضاعفت المعطيات (حجم الكتاب) في هذا المثال زادت مدّة البحث بشكل قليل.