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

لماذا نستخدم تدوين Big O؟

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

مثال: جمع الأعداد

دعونا نستكشف طريقتين لحساب مجموع كل الأرقام من 1 إلى n:

الخيار 1: استخدام حلقة

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i 




  
  
  الخيار 2: استخدام الصيغة




function addUpTo(n) {
    return n * (n   1) / 2;
}





  
  
  تحليل التعقيد


في الخيار 1، إذا كانت n تساوي 100، فسيتم تشغيل الحلقة 100 مرة. في المقابل، الخيار 2 ينفذ دائمًا عددًا ثابتًا من العمليات (الضرب والجمع والقسمة). هكذا:

• الخيار 1 هو O(n): ينمو التعقيد الزمني خطيًا مع n.
• الخيار 2 هو O(1): يظل التعقيد الزمني ثابتًا، بغض النظر عن حجم الإدخال.

تنصل

بينما يتضمن الخيار 2 ثلاث عمليات (الضرب، الجمع، القسمة)، فإننا نركز على الاتجاه العام في تحليل Big O. وبالتالي، بدلًا من التعبير عنها بـ O(3n)، نقوم بتبسيطها إلى O(n). وبالمثل، O(n 10) يبسط إلى O(n)، وO(n^2 5n 8) يبسط إلى O(n^2). في Big O Notation، نأخذ في الاعتبار السيناريو الأسوأ، حيث يكون للمصطلح الأعلى تأثيرًا على الأداء.

هناك أشكال أخرى من التدوين تتجاوز التعقيدات الشائعة المذكورة أعلاه، مثل التعقيد الزمني اللوغاريتمي المعبر عنه بـ O(log n).

ما هو تدوين كبير يا؟

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

• الوقت الثابت: O(1) - لا يتغير أداء الخوارزمية مع حجم الإدخال.
• الوقت الخطي: O(n) - ينمو الأداء خطيًا مع حجم الإدخال.
• الزمن التربيعي: O(n^2) - ينمو الأداء بشكل تربيعي مع زيادة حجم الإدخال.

مثال على O(n^2)

خذ بعين الاعتبار الدالة التالية، التي تطبع جميع أزواج الأرقام من 0 إلى n:

function printAllPairs(n) {
    for (var i = 0; i 



في هذه الحالة، تحتوي الدالة على حلقتين متداخلتين، لذلك عندما يزيد nnn، يزيد عدد العمليات بشكل تربيعي. بالنسبة لـ n=2، هناك 4 عمليات، وبالنسبة لـ n=3، هناك 9 عمليات، مما يؤدي إلى O(n^2).


  
  
  مثال آخر: العد لأعلى ولأسفل




function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i = 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}





 للوهلة الأولى، قد يعتقد المرء أن هذا هو O(n^2) لأنه يحتوي على حلقتين. ومع ذلك، تعمل كلتا الحلقتين بشكل مستقل وتتدرجان خطيًا باستخدام n. وبالتالي، فإن التعقيد الزمني الإجمالي هو O(n).


  
  
  تبسيط التحليل


قد يكون تحليل كل جانب من جوانب تعقيد التعليمات البرمجية أمرًا معقدًا، ولكن يمكن لبعض القواعد العامة تبسيط الأمور:

• تعتبر العمليات الحسابية زمناً ثابتاً.
• التكليفات المتغيرة هي زمن ثابت.
• الوصول إلى العناصر في مصفوفة (عن طريق الفهرس) أو الكائن (عن طريق المفتاح) هو وقت ثابت.
• بالنسبة للحلقة، التعقيد هو طول الحلقة مضروبًا في تعقيد ما يحدث داخل الحلقة.

تعقيد الفضاء

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

قواعد تعقيد الفضاء (استنادا إلى جافا سكريبت):

• معظم القيم البدائية (القيم المنطقية، والأرقام، وما إلى ذلك) هي مساحة ثابتة.
• تتطلب السلاسل مسافة O(n) (حيث n هو طول السلسلة).
• أنواع المراجع (المصفوفات، الكائنات) هي بشكل عام O(n)، حيث n هو طول المصفوفة أو عدد المفاتيح في الكائن.

مثال

function sum(arr) {
    let total = 0;
    for (let i = ; i 



في هذه الدالة، تعقيد المساحة هو O(1) لأننا نستخدم مقدارًا ثابتًا من المساحة (متغيرين) بغض النظر عن حجم الإدخال.

للحصول على دالة تقوم بإنشاء مصفوفة جديدة:



function double(arr) {
    let newArr = [];
    for (let i = 0; i 



هنا، تعقيد المساحة هو O(n) لأننا نخصص مساحة لمصفوفة جديدة تنمو مع حجم مصفوفة الإدخال.


  
  
  خاتمة


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