تدوين كبير في بنية البيانات: كل شيء يجب معرفته

يتم استخدام تدوين Big O في بنية البيانات لتحديد كفاءة الخوارزمية ، ومقدار الوقت الذي يستغرقه تشغيل الوظيفة مع نمو المدخلات ، ومدى جودة مقاييس الوظيفة. يمكن تقسيم قياس هذه الكفاءة إلى جزأين ، وهما التعقيد المكاني وتعقيد الوقت.

يشير تدوين Big O إلى التدوين الرياضي الذي يعمل كعامل مقيد لأي دالة عندما تكون الحجة أكثر عرضة للانحراف نحو قيمة محددة أو ما لا نهاية. إنه ينتمي إلى فئة الرموز الرياضية التي اخترعها إدموند لانداو وبول باخمان وآخرين. ومن ثم ، يطلق عليه بشكل جماعي تدوين باخمان-لانداو أو الترميز المقارب.

وفقًا للخصم الرياضي ، يتم تحديد وظيفتين ، f (n) و g (n) على مجموعة من الأرقام الموجبة أو الحقيقية غير المقيدة. هنا ، g (n) موجبة تمامًا لكل قيمة كبيرة لـ n. يمكن كتابتها بالطريقة التالية:

f (n) = O (g (n)) حيث يميل n إلى اللانهاية (n → ∞)

ومع ذلك ، هنا ، لم يتم تعريف افتراض n إلى ما لا نهاية بشكل حصري ، وبالتالي يمكن كتابة التعبير أعلاه على النحو التالي:

و (ن) = O (ز (ن))

هنا ، f و g هما الدالتان الضروريتان اللتان تبدأان من الأعداد الصحيحة الموجبة إلى الأعداد الحقيقية غير السالبة.

ومن ثم ، يتم الإشارة إلى قيم n الكبيرة بواسطة مقارب Big O.

خصائص تدوين Big O في بنية البيانات

تحتوي خوارزمية Big O في بنية البيانات على عدد قليل جدًا من الخصائص المطلوبة إلزاميًا. الخصائص الأساسية المذكورة لترميز Big O هي كما يلي:

• وظيفة الجمع:
  إذا كانت f (n) = f 1 (n) + f 2 (n) + - + f m (n) و f i (n) ≤ f i +1 (n) ∀ i = 1 ، 2 ، - ، m ،
  ثم O (f (n)) = O (حد أقصى (f1 (n) ، f2 (n) ، - ، fm (n))).
• الوظيفة اللوغاريتمية:
  إذا كانت f (n) = logan و g (n) = logbn ،
  ثم O (f (n)) = O (g (n))
• الضرب المستمر:
  إذا كانت f (n) = cg (n) ، إذن O (f (n)) = O (g (n)) حيث c هو ثابت غير صفري.
• الدالة متعددة الحدود:
  إذا كانت f (n) = a0 + a1.n + a2.n2 + - + am.nm ،
  ثم O (f (n)) = O (نانومتر).

تعلم دورات تطوير البرمجيات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.

استكشف دوراتنا التدريبية الشهيرة في هندسة البرمجيات

هنا ، أثناء معالجة Big O ، تزداد كل وظيفة سجل مفردة بالمثل.

أهمية تدوين Big O في تحليل وقت التشغيل للخوارزميات

تُستخدم تعقيدات وقت تشغيل الخوارزمية في أسوأ الحالات لإجراء المقارنات والحساب ، خاصة في حالة تحليل أداء الخوارزمية. يعتبر ترتيب O (1) ، الذي تم تصويره على أنه وقت التشغيل الثابت ، هو أسرع وقت تشغيل للخوارزمية - الوقت الذي تستغرقه الخوارزمية هو نفسه بالنسبة لأحجام الإدخال المختلفة. من المهم ملاحظة أن وقت التشغيل المثالي للخوارزمية هو وقت التشغيل الثابت ، والذي نادرًا ما يتحقق لأن وقت تشغيل الخوارزمية يعتمد على حجم إدخال n.

فمثلا:

كما ذكرنا سابقًا ، يعتمد أداء وقت تشغيل الخوارزمية بشكل كبير على حجم إدخال n. دعونا نوضح هذه الحقيقة ببعض الأمثلة الرياضية لإجراء تحليل وقت التشغيل لخوارزمية لأحجام مختلفة من n:

• ن = 20
  تسجيل (20) = 2.996 ؛
  20 = 20 ؛
  20 سجل (20) = 59.9 ؛
  20 2 = 400 ؛
  2 20 = 1084576 ؛
  20! = 2.432902 + 18 18 ؛
• ن = 10
  تسجيل (10) = 1 ؛
  10 = 10 ؛
  10 سجل (10) = 10 ؛
  10 2 = 100 ؛
  2 10 = 1024 ؛
  10! = 3628800 ؛

يتم حساب أداء وقت تشغيل الخوارزمية بالمثل.

فيما يلي بعض الأمثلة الحسابية الأخرى لتحليل وقت التشغيل -

• عندما يتعلق الأمر بـ Linear Search ، فإن تعقيد وقت التشغيل هو O (n).
• تعقيد وقت التشغيل هو O (تسجيل الدخول) للبحث الثنائي.
• بالنسبة لـ Selection Sort و Bubble Sort و Bucket Sort و Insertion Sort ، يكون تعقيد وقت التشغيل هو O (n ^ c).
• عندما يتعلق الأمر بالخوارزميات الأسية مثل برج هانوي ، فإن تعقيد وقت التشغيل هو O (c ^ n).
• بالنسبة إلى Merge SortSort و Heap Sort ، يكون تعقيد وقت التشغيل هو O (n log n).

كيف يحلل Big O تعقيد الفضاء؟

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

لتحديد مدى تعقيد مساحة الخوارزمية ، يجب أن نتبع هاتين المهمتين -

المهمة 1: من الضروري تنفيذ البرنامج لخوارزمية معينة.

المهمة 2: من الضروري معرفة حجم الإدخال n لتحديد الذاكرة التي سيحتفظ بها كل عنصر.

تتطلب هاتان المهمتان الأساسيتان إنجازهما قبل حساب التعقيد المكاني للخوارزمية.

أمثلة على خوارزميات تعقيد الفضاء

هناك العديد من الأمثلة على الخوارزميات ذات التعقيد المكاني ، وقد تم ذكر بعضها أدناه من أجل فهم أفضل لهذا النوع من الخوارزمية:

• بالنسبة لفرز الفقاعات والبحث الخطي وفرز التحديد وفرز الإدراج وفرز الكومة والبحث الثنائي ، يكون تعقيد المساحة هو O (1) .
• تعقيد الفضاء هو O (n + k) عندما يتعلق الأمر بفرز الجذر .
• تعقيد المساحة هو O (n) لـ SortSort السريع.
• تعقيد المساحة هو O (log n) لفرز الدمج.

مثال على تدوين Big O في لغة C.

إنها حقيقة أن تدوين Big O يستخدم بشكل أساسي في علوم الكمبيوتر لتحديد مدى تعقيد أو أداء الخوارزمية. يوفر لنا هذا الترميز القدرة على تصنيف سلوك الخوارزميات بناءً على نمو مساحة الذاكرة أو متطلبات وقت التنفيذ عندما يصبح حجم بيانات الإدخال كبيرًا. لم يتم تصميمه للتنبؤ بالاستخدام الفعلي للذاكرة أو وقت التنفيذ ولكن لمقارنة الخوارزميات ثم اختيار الأفضل بينها للوظيفة. إنه ليس خاصًا باللغة ولكن يتم تنفيذه أيضًا في C.

أدناه ، ستجد خوارزمية فرز التحديد في C حيث تم حساب التعقيد الأسوأ (تدوين Big O) للخوارزمية: -

لـ (int i = 0 ؛ i <n ؛ i ++)

{

كثافة العمليات دقيقة = أنا ؛

لـ (int j = i ؛ j <n ؛ j ++)

{

إذا (مجموعة [ي] <مجموعة [دقيقة])

دقيقة = ي ؛

}

int temp = مجموعة [i] ؛

مجموعة [i] = صفيف [دقيقة] ؛

مجموعة [دقيقة] = درجة الحرارة ؛

}

لتحليل الخوارزمية:

• يمكن بالفعل الإشارة إلى أن نطاق الحلقة الخارجية هو i <n ، مما يشير إلى أن ترتيب الحلقة هو O (n).
• بعد ذلك ، يمكننا تحديد أنه أيضًا O (n) مثل j <n لحلقة for الداخلية.
• يتم تجاهل الثابت ، حتى لو تم العثور على متوسط ​​الكفاءة n / 2 لـ c ثابت. إذن ، الترتيب هو O (n).
• بعد ضرب ترتيب الحلقة الداخلية والحلقة الخارجية ، يكون تعقيد وقت التشغيل الذي تم تحقيقه هو O (n ^ 2).

يمكن تنفيذ الخوارزميات الأخرى في لغة سي بسهولة ، حيث يمكن بسهولة تحليل التعقيدات وتحديدها بالمثل.

استخدام تدوين Big O

هناك مجالان رئيسيان يتم فيهما تطبيق تدوين Big O: -

• الرياضيات : يستخدم تدوين Big O بشكل شائع في مجال الرياضيات لوصف كيف تقترب سلسلة منتهية بشكل وثيق من وظيفة ، خاصة عندما يتعلق الأمر بحالات التوسع المقارب أو سلسلة تايلور المبتورة.
• علوم الكمبيوتر: من الحقائق الراسخة أن تدوين Big O يستخدم في الغالب في مجال علوم الكمبيوتر نظرًا لفائدته في تحليل الخوارزميات

ومع ذلك ، في كلا التطبيقين ، غالبًا ما يتم اختيار الوظيفة g ( x ) التي تظهر داخل O (·) لتكون الأكثر بساطة إذا تم حذف شروط الترتيب الأدنى والعوامل الثابتة.

هناك استخدامان آخران لهذا الترميز قريبان رسميًا ولكنهما مختلفان نسبيًا. هم انهم:-

• مقارب لانهائي
• المقاربة متناهية الصغر.

ومع ذلك ، فإن هذا التمييز ليس من حيث المبدأ ، من حيث التطبيق فقط مع التعريف الرسمي لـ "Big O" هو نفسه بالضبط في كلتا الحالتين. الاختلاف الوحيد هو حدود وسيطة الدالة.

اقرأ مقالاتنا الشهيرة المتعلقة بتطوير البرمجيات

استنتاج

في الختام ، يمكننا القول أن البيانات الضخمة تلعب دورًا أساسيًا في هياكل البيانات ، وأن امتلاك معرفة متعمقة وشاملة حول تدوين Big O هو مهارة ممتازة يجب امتلاكها. يزداد الطلب عليه في قطاع العمل ويمكن أن يكون خيارًا رائعًا لمسار وظيفي. سيمنحك برنامج الشهادة المتقدمة في البيانات الضخمة من upGrad النفوذ الذي تحتاجه لتعزيز حياتك المهنية. سيقدم لك أفضل المهارات المهنية مثل معالجة البيانات باستخدام PySpark ، وتخزين البيانات ، و MapReduce ، ومعالجة البيانات الكبيرة على AWS Cloud ، والمعالجة في الوقت الفعلي ، وما إلى ذلك.