algorithm - عربي - امثلة على big-o




Big O ، كيف تحسبه/تقربه؟ (15)

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

لكنني أشعر بالفضول ، كيف تحسب أو تقارب تعقيد الخوارزميات الخاصة بك؟

1 ولكن كما يقولون ، لا تفرط في ذلك ، فإن التحسين المبكر هو أصل كل الشرور ، والتحسين دون سبب مبرر يجب أن يستحق هذا الاسم أيضًا.


أساسا الشيء الذي يحصد 90 ٪ من الوقت هو مجرد تحليل الحلقات. هل لديك حلقات متداخلة مفردة ومزدوجة وثلاثية؟ لديك O (n) ، O (n ^ 2) ، O (n ^ 3) وقت التشغيل.

نادرًا جدًا (ما لم تكن تكتب نظامًا أساسيًا يحتوي على مكتبة أساسية واسعة النطاق (على سبيل المثال ، .NET BCL ، أو STL الخاص بـ C ++) ، فسوف تواجه أي شيء أصعب من مجرد النظر إلى الحلقات (في عبارات ، بينما ، goto ، إلخ...)


أفكر في ذلك من حيث المعلومات. أي مشكلة تتكون من تعلم عدد معين من البتات.

أداتك الأساسية هي مفهوم نقاط القرار وانتروبيا. إن إنتروبيا نقطة القرار هي متوسط ​​المعلومات التي ستقدمها لك. على سبيل المثال ، إذا كان البرنامج يحتوي على نقطة قرار بفرعين ، فإن الإنتروبيا هي مجموع احتمال كل فرع من المرات في السجل 2 للاحتمال العكسي لهذا الفرع. هذا هو مقدار ما تتعلمه من خلال تنفيذ هذا القرار.

على سبيل المثال ، if العبارة التي تحتوي على فرعين ، كلاهما متساويين على الأرجح ، فلها انتروبيا من 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. لذلك الكون هو 1 بت.

افترض أنك تبحث في جدول عناصر N ، مثل N = 1024. هذه مشكلة 10 بت لأن السجل (1024) = 10 بت. لذا ، إذا كان بإمكانك البحث باستخدام عبارات IF التي لها نتائج متساوية ، يجب أن تتخذ 10 قرارات.

هذا ما تحصل عليه مع البحث الثنائي.

افترض أنك تقوم بالبحث الخطي. تنظر إلى العنصر الأول وتسأل ما إذا كان هو الذي تريده. الاحتمالات هي 1/1024 وهذا هو ، و 1023/1024 أنها ليست كذلك. الكون من هذا القرار هو 1/1024 * سجل (1024/1) + 1023/1024 * سجل (1024/1023) = 1/1024 * 10 + 1023/1024 * حوالي 0 = حوالي 0.1 بت. لقد تعلمت القليل جدا! القرار الثاني ليس أفضل بكثير. هذا هو السبب في أن البحث الخطي بطيء للغاية. في الواقع ، إنها قيمة أصلية في عدد البتات التي تحتاج إلى تعلمها.

افترض أنك تقوم بفهرسة. لنفترض أن الجدول يتم فرزه مسبقًا في الكثير من الصناديق ، ويمكنك استخدام بعض البتات في المفتاح للفهرسة مباشرة إلى إدخال الجدول. إذا كانت هناك صناديق 1024 ، فإن الإنتروبيا هي 1/1024 * log (1024) + 1/1024 * log (1024) + ... لجميع النتائج الممكنة 1024. هذا هو 1/1024 * 10 مرات النتائج 1024 ، أو 10 بتات من الإنتروبيا لعملية الفهرسة واحدة. هذا هو سبب فهرسة البحث بسرعة.

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

لذلك ، تستند الأنواع المستندة إلى القرارات الثنائية التي تحتوي على نتائج متساوية تقريباً على خطوات O (N log N). خوارزمية الفرز O (N) ممكن إذا كان يعتمد على البحث الفهرسة.

لقد وجدت أنه يمكن النظر في جميع مشكلات الأداء الخوارزمية تقريبًا بهذه الطريقة.


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

لا يوجد أي إجراء ميكانيكي يمكن استخدامه للحصول على BigOh.

باعتبارك "كتاب طبخ" ، للحصول على BigOh من جزء من التعليمات البرمجية ، عليك أولاً أن تدرك أنك تقوم بإنشاء صيغة حسابية لحساب عدد خطوات تنفيذ العمليات الحسابية ، وذلك نظرًا لإدخال حجم معين.

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

على سبيل المثال ، لنفترض أنك تمتلك هذه الشفرة:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

تقوم هذه الدالة بارجاع مجموع كل عناصر المصفوفة ، ونريد تكوين صيغة لحساب التعقيد الحسابي لهذه الوظيفة:

Number_Of_Steps = f(N)

لذلك لدينا f(N) ، دالة لحساب عدد الخطوات الحسابية. مدخلات الدالة هي حجم البنية المراد معالجتها. هذا يعني أن هذه الوظيفة تسمى:

Number_Of_Steps = f(data.length)

تأخذ المعلمة N قيمة data.length . الآن نحن بحاجة إلى التعريف الفعلي للدالة f() . يتم ذلك من شفرة المصدر ، حيث يتم ترقيم كل سطر مثير من 1 إلى 4.

هناك العديد من الطرق لحساب BigOh. من الآن فصاعدًا ، سنفترض أن كل جملة لا تعتمد على حجم بيانات الإدخال تأخذ خطوات حسابية ثابتة من C

سنقوم بإضافة العدد الفردي لخطوات الوظيفة ، ولن يعتمد تعريف المتغير المحلي أو بيان الإرجاع على حجم صفيف data .

وهذا يعني أن الخطين 1 و 4 يأخذان C من الخطوات لكل منهما ، والوظيفة تشبه إلى حد ما ما يلي:

f(N) = C + ??? + C

الجزء التالي هو تحديد قيمة البيان. تذكر أننا نحصي عدد الخطوات الحسابية ، بمعنى أن يتم تنفيذ نص البيان for N مرات. هذا هو نفس إضافة C ، N مرات:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

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

للحصول على BigOh الفعلي نحتاج إلى تحليل مقارب للوظيفة. يتم ذلك تقريبًا على النحو التالي:

  1. يسلب كل الثوابت C .
  2. من f() احصل على polynomium في شكله standard form .
  3. اقسم شروط polynomium وفرزها حسب معدل النمو.
  4. ابق على الشخص الذي يكبر عندما يقترب N infinity .

لدينا f() لديها فترتين:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

التخلص من جميع ثوابت C والأجزاء الزائدة:

f(N) = 1 + N ^ 1

بما أن المصطلح الأخير هو الذي ينمو أكبر عندما يقترب f() اللانهاية (عند التفكير في limits ) فإن هذه هي الوسيطة BigOh ، ووظيفة sum() لها BigOh:

O(N)

هناك بعض الحيل لحل بعض الخدع: استخدم summations كلما استطعت.

على سبيل المثال ، يمكن حل هذه الشفرة بسهولة باستخدام المجموعات:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

أول شيء يجب أن يُطلب منك هو أمر تنفيذ foo() . في حين أن المعتاد هو أن تكون O(1) ، فأنت بحاجة إلى أن تسأل أساتذتك عن ذلك. O(1) تعني (تقريبا ، معظمها) ثابتة C ، مستقلة عن حجم N

البيان عن الجملة رقم واحد هو صعب. بينما ينتهي المؤشر في 2 * N ، تتم الزيادة من قبل اثنين. وهذا يعني أن أول ما يتم تنفيذه هو N الخطوات فقط ، ونحن بحاجة إلى تقسيم العد إلى اثنين.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

الجملة رقم اثنين حتى أكثر تعقيدا لأنها تعتمد على قيمة i . إلقاء نظرة: يأخذ مؤشر أنا القيم: 0 ، 2 ، 4 ، 6 ، 8 ، ... ، 2 * N ، والثانية for على تنفيذها: N مرات الأولى ، N - 2 الثانية ، N - 4 والثالث ... حتى مرحلة N / 2 ، والتي لم يتم تنفيذ الثاني أبدا.

على صيغة ، وهذا يعني:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

مرة أخرى ، نحن نحسب عدد الخطوات . وبحسب التعريف ، يجب أن يبدأ كل جمع دائمًا في واحد ، وينتهي عند رقم أكبر أو يساوي واحد.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(نحن نفترض أن foo() هو O(1) ويأخذ خطوات C )

لدينا مشكلة هنا: عندما أتناول القيمة N / 2 + 1 لأعلى ، ينتهي التلخيص الداخلي برقم سالب! هذا مستحيل وخاطئ. نحن بحاجة إلى تقسيم الجمع في اثنين ، كونها نقطة محورية في اللحظة التي تتخذ N / 2 + 1 .

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

منذ اللحظة المحورية i > N / 2 ، لن يتم تنفيذ الجزء الداخلي for ، ونفترض وجود تعقيد ثابت لتنفيذ C على جسمه.

الآن يمكن تبسيط عمليات الجمع باستخدام بعض قواعد الهوية:

  1. Summation (w 1 to N) (C) = N * C
  2. جمع (w من 1 إلى N) (A (+/-) B) = جمع (w من 1 إلى N) (A) (+/-) Summ (من 1 إلى N) (B)
  3. ملخص (w من 1 إلى N) (w * C) = C * Summation (w من 1 إلى N) (w) (C هو ثابت ومستقل عن w )
  4. Summation (w 1 to N) (w) = (N * (N + 1)) / 2

تطبيق بعض الجبر:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

و BigOh هو:

O(N²)

إذا كانت تكلفتك متعددة الحدود ، فاحفظ المصطلح الأعلى ترتيبًا ، بدون مضاعفه. على سبيل المثال:

O ((n / 2 + 1) * (n / 2)) = O (n 2/4 + n / 2) = O (n 2/4) = O (n 2 )

هذا لا يعمل لسلسلة لا نهائية ، فكر فيك. لا توجد وصفة واحدة للحالة العامة ، على الرغم من بعض الحالات الشائعة ، تنطبق عدم المساواة التالية:

O (log N ) <O ( N ) <O ( N log N ) <O ( N 2 ) <O ( N k ) <O (e n ) <O ( n !)


الإلمام بالخوارزميات / هياكل البيانات التي أستخدمها و / أو تحليل النظرة السريعة لتداخل التكرار. وتكمن الصعوبة في ذلك عندما تتصل بوظيفة مكتبة ، وربما عدة مرات - فغالباً ما تكون غير متأكد مما إذا كنت تتصل بالوظيفة دون داعٍ في بعض الأحيان أو ما هي التطبيقات التي تستخدمها. ربما يجب أن يكون لوظائف المكتبة تدبير معقد / كفاءة ، سواء كان ذلك Big O أو أي مقياس آخر ، متوفر في الوثائق أو حتى IntelliSense .


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

كمثال بسيط للغاية يقول أنك تريد القيام بفحص سلامة العقل على سرعة ترتيب قائمة .NET framework. يمكنك كتابة شيء مثل ما يلي ، ثم تحليل النتائج في Excel للتأكد من أنها لم تتجاوز منحنى n * log (n).

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

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

بالنسبة للحالة الأولى ، يتم تنفيذ الحلقة الداخلية ni times ، وبالتالي فإن إجمالي عدد عمليات الإعدام هو مجموع لذهاب من 0 إلى n-1 (لأن أقل من ، أو ليس أقل من أو يساوي) من ni . ستحصل في النهاية على n*(n + 1) / 2 ، لذا O(n²/2) = O(n²) .

للحلقة الثانية ، بين 0 و n متضمنة في الحلقة الخارجية ؛ ثم يتم تنفيذ الحلقة الداخلية عندما يكون j أكبر بشكل صارم من n ، والذي يكون مستحيلاً.


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

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

لاحظ أن الثابت الخفي يعتمد كثيرا على التنفيذ!

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

هناك تعقيدات زمنية مختلفة:

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

  • ...

مقدمة جيدة هي مقدمة لتحليل الخوارزميات بواسطة R. Sedgewick و P. Flajolet.

وكما تقول ، فإن premature optimisation is the root of all evil ، ويجب دائمًا استخدام التنميط (إن أمكن) عند تحسين الكود. ويمكن أن يساعدك أيضًا في تحديد مدى تعقيد الخوارزميات.


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

في ما يلي بعض الحالات الأكثر شيوعًا ، والتي تم رفعها من http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) - تحديد ما إذا كان الرقم متساويًا أو فرديًا ؛ باستخدام جدول بحث ذي حجم ثابت أو جدول تجزئة

O (logn) - البحث عن عنصر في مصفوفة مرتبة باستخدام بحث ثنائي

O (n) - البحث عن عنصر في قائمة لم يتم فرزها ؛ إضافة رقمين n-digit

O (n 2 ) - ضرب رقمين n-digit بواسطة خوارزمية بسيطة ؛ إضافة اثنين من المصفوفات ن × ن. نوع فقاعة أو نوع الإدراج

O (n 3 ) - ضرب اثنين من المصفوفات ن × عن طريق خوارزمية بسيطة

O (c n ) - إيجاد الحل (الدقيق) لمشكلة البائع المتجول باستخدام البرمجة الديناميكية ؛ تحديد ما إذا كان هناك عبارات منطقية متساوية باستخدام القوة الغاشمة

O (n!) - حل مشكلة مندوب المبيعات عبر البحث عن القوة الغاشمة

O (n n ) - غالباً ما تستخدم بدلاً من O (n!) لاستخلاص صيغ أبسط للتعقيد التقاربي


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

وأود أيضا أن أضيف كيف يتم ذلك من أجل الوظائف العودية :

لنفترض أن لدينا وظيفة مثل ( رمز النظام ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

الذي يحسب بشكل متكرر العاملية رقم معين.

الخطوة الأولى هي محاولة تحديد خصائص الأداء لجسم الوظيفة فقط في هذه الحالة ، لا يتم عمل أي شيء خاص في الجسم ، فقط ضرب (أو إرجاع القيمة 1).

إذن أداء الجسم هو: O (1) (ثابت).

حاول بعد ذلك وتحديد هذا العدد من المكالمات المتكررة . في هذه الحالة لدينا نداءات متكررة n-1.

لذا فإن أداء المكالمات العودية هو: O (n-1) (الترتيب n ، حيث نرمي الأجزاء غير المهمة).

ثم ضع هذين الاثنين معًا ثم لديك الأداء للدالة العودية بالكامل:

1 * (n-1) = O (n)

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


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

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

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


ما غالبًا ما يتم تجاهله هو السلوك المتوقع لخوارزمياتك. لا يغير Big-O من الخوارزمية الخاصة بك ، ولكنه يرتبط بالعبارة "تحسين سابق لأوانه.. .."

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

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

لتلطيخها حقًا ، عليك أن تكون قادرًا على وصف توزيع احتمالية "مساحة الإدخال" (إذا كنت بحاجة إلى فرز قائمة ، فكم مرة يتم تصنيف تلك القائمة بالفعل؟ كم مرة يتم عكسها تمامًا؟ often is it mostly sorted?) It's not always feasible that you know that, but sometimes you do.


يعطي Big O الحد الأعلى لتعقيد وقت الخوارزمية. وعادة ما يتم استخدامه بالتزامن مع معالجة مجموعات البيانات (القوائم) ولكن يمكن استخدامها في مكان آخر.

بعض الأمثلة على كيفية استخدامه في كود C.

لنفترض أن لدينا مجموعة من العناصر n

int array[n];

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

x = array[0];

إذا أردنا العثور على رقم في القائمة:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

سيكون هذا هو O (n) لأنه على الأكثر يجب أن ننظر إلى القائمة بأكملها للعثور على رقمنا. لا يزال الـ Big-O O (n) على الرغم من أننا قد نجد رقمنا هو المحاولة الأولى ونجري من خلال الحلقة مرة واحدة لأن Big-O يصف الحد الأعلى لخوارزمية (أوميغا هو لحد أدنى و ثيتا لربط ضيق) .

عندما نصل إلى الحلقات المتداخلة:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

هذا هو O (n ^ 2) نظرًا لأن كل مسار للحلقة الخارجية (O (n)) يجب علينا أن نمر عبر القائمة بأكملها مرة أخرى حتى تتضاعف n تاركة لنا مع n squared.

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


For code A, the outer loop will execute for n+1 times, the '1' time means the process which checks the whether i still meets the requirement. And inner loop runs n times, n-2 times.... Thus, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

For code B, though inner loop wouldn't step in and execute the foo(), the inner loop will be executed for n times depend on outer loop execution time, which is O(n)


great question!

If you're using the Big O, you're talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Ok, so now what do we mean by "best-case" and "worst-case" complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it'll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.







performance