ما الهدف الأساسي للـ BigO ؟ وعن ماذا تعبر تحديدًا ؟

لماذا عندما نجد loop تلف 1000000 لفة نقول O(1) ؟

وعندما نجد نفس الـ loop تلف n لفة نقول O(n) ؟

سنجاوب على السؤال بمثال بسيط يوضح الفكرة الأساسية من الـ BigO

تبسيط الفكرة

لنفترض انك انضمت لشركة ناسا والحمد لله، وأخبروك أنهم يريدون منك أن تقوم بعمل بعض العمليات على الكواكب في مجموعتنا الشمسية

فناسا طلبت منك أن تطبع اسامي الكواكب فقط

نحن نعرف أن عدد الكواكب في مجموعتنا الشمسية 8 وهو عدد ثابت لن يتغير

for (int i = 0; i < 8; i += 1) {
  cout << planets[i].name <<' ';
}

هنا قمنا بعمل فورة جميلة تلف على الكواكب حيث أن planets[i] يمثل object للكوكب رقم i

كما ترى فتحت فقط طبعنا الإسم دون مشاكل

هنا الـ BigO تساوي O(8) التي تعني انها تساوي O(1), لان 8 رقم ثابت ومعلوم لدينا

ناسا قالت لك أنها تريد الآن طباعة اسم كل كوكب وطباعة عدد الكواكب الذي يملكون نفس عدد الاقمار هذا الكوكب

بمعنى أنه لو كوكب الارض يملك قمر واحد فاطبع اسم كوكب الارض وبجانبه عدد الكواكب الذين يملكون قمر واحد مثله

for (int i = 0; i < 8; i += 1) {
  int countPlanets = 0;
  for (int j = 0; j < 8; j += 1)
    if (planets[i].numberOfMoons == planets[j].numberOfMoons)
      countPlanets += 1;

    cout <<" No. Planets that have the same No. moons of planet " << planets[i].name
         << " are: "<<  countPlanets << '\n';
}

هنا الـ BigO ستكون O(64) التي ستكون أيضا O(1)

لأن عدد الكواكب ثابت ومعلوم لدينا وهو 8 وليس رقمًا مجهولًا لذا قلنا انه O(1)

حتى اذا زودنا عدد الفورات هنا ستظل دائما O(1)، لماذا ؟

لانه عدد ثابت معلوم أنت تعرف أنه دائما سيكون 8 بالتالي انت لن تخاف من أن يزيد أو ينقص

لأنه ليس هناك عامل مجهول في المعادلة بالتالي يمكنك إنشاء أي كود يتعامل مع عدد الـ 8 كواكب فقط بشكل خاص

وانت تعلم مسبقًا امكانيات الكود وحدوده وتعرف انه لن يزيد أو ينقص لانك تتعامل مع قيم معلومة وثابتة وليست متغيرة ومجهولة

ظهور المشكلة مع القيم المتغيرة

متى يكون الأمر فيه مشكلة ؟ عندما تتعامل مع مجهول بقيم متغيرة

لنفرض أن ناسا قالت لك اننا نريد نفس الكود نطبقه على جميع الأنظمة الشمسية والمجرات التي نعرفها

الآن كم عدد الكواكب هنا ؟ ستقول لي n هنا أنت تخاف وتبدأ بأخذ حذرك لأنك الآن تتعامل مع مجهول بالتالي قيم دائمة التغير

الكود السابق لنفترض أنك جعلته يتعامل مع ثابت وهو حين كان عدد الكواكب 8 فقط

وكنت مطمئن بأنه ثابت فكنت على يقين تام أنه لن يزيد ولن ينقص، فكتبت كود يناسب الرقم 8 فقط لا غير

الآن في الكود السابق إن استبدلنا الرقم 8 بـ n فالـ BigO سيكون O(n²) ما معنى هذا ؟

الـ BigO يتعامل مع القيم والمعطيات المتغيرة فقط ويخبرك بأسوء حالة ممكن أن يتعامل معها كودك

لو كان عدد الكواكب n = 1000 فالـ n² = 1000000 لذلك الـ BigO سينبهك ويحذرك كيف سيتعامل كودك مع المعطيات المتغيرة التي ستأتيه

عندما كان الكود محصورًا لمجموعتنا الشمسية 8 كواكب فلم يكن هناك أي مجهول لقيم متغيرة، بالتالي فلا يوجد أي خوف أو مخاطر لقيم متغيرة غير متوقعة
فأنت هنا مع الـ BigO تبدأ بالتفكير بكيفية تحسين الكود ليتناسب مع القيم المتغيرة بدلًا من الثابتة

مراجعة واجابة للسؤال الذي بدأنا به

فإجابة اول سؤال سألناه وهو:

  • لماذا عندما نجد loop تلف 1000000 لفة نقول O(1)
  • نقول: لانه قيمة ثابتة ومعلومة لدينا
  • فيمكننا أن نتعامل معه كيفما نريده دون الخوف منه
  • لانه لن يزيد او ينقص بل سيظل كما هو فسنقوم بعمل كود يناسبه هو فقط
  • ولماذا عندما نجد نفس الـ loop تلف n لفة نقول O(n)
  • نقول: لأننا نتعامل مع متغير مجهول ليس ثابت وقيمته ستكون مختلفة كل مرة
  • فهنا نحاول أن نقوم بعمل كود يناسب كل الحالات ونحاول أن نقلل دائما الـ BigO
فتذكر أن الـ BigO يتعامل مع القيم المجهولة فقط ويصف لك اسوء حالة سيتعامل معها كودك