سؤال

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

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

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

هل كانت مفيدة؟

المحلول

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


لا يوجد الإجراء الميكانيكي التي يمكن استخدامها للحصول على 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 يأخذان عددًا من الخطوات لكل منهما، والدالة تشبه إلى حد ما هذا:

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

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

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

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

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

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

ملكنا f() له مصطلحان:

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

أخذ كل C الثوابت والأجزاء الزائدة:

f(N) = 1 + N ^ 1

لأن الفصل الأخير هو الذي يكبر متى f() يقترب من اللانهاية (فكر في حدود) هذه هي حجة BigOh، و sum() الدالة لها BigOh من:

O(N)

هناك بعض الحيل لحل بعض المشكلات الصعبة:يستخدم الجمع كلما استطعت.

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

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.

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

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

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

في الصيغة يعني:

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 خطوات.)

لدينا مشكلة هنا:متى i يأخذ القيمة N / 2 + 1 صعودا، وينتهي الجمع الداخلي عند رقم سلبي!وهذا مستحيل وخاطئ.نحن بحاجة إلى تقسيم الجمع إلى قسمين، كونها النقطة المحورية في هذه اللحظة i يأخذ 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. الجمع(ث من 1 إلى ن)(ج) = ن * ج
  2. الجمع(ث من 1 إلى N)( A (+/-) B ) = الجمع(w من 1 إلى N)( A ) (+/-) الجمع(w من 1 إلى N)( B )
  3. الجمع(ث من 1 إلى N)(w * C) = C * الجمع(w من 1 إلى N)(w) (C ثابت، مستقل عن w)
  4. الجمع(ث من 1 إلى 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²)

نصائح أخرى

يعطي 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 تربيع.

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

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

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

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

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

O(n) - البحث عن عنصر في قائمة غير مصنفة؛إضافة رقمين مكونين من رقم n

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

على3) - ضرب مصفوفتين n×n باستخدام خوارزمية بسيطة

يا(جن) - إيجاد الحل (الدقيق) لمشكلة البائع المتجول باستخدام البرمجة الديناميكية.تحديد ما إذا كانت عبارتان منطقيتان متكافئتان باستخدام القوة الغاشمة

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

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

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

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

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

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

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

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

  • ...

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

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

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

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

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

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

الذي يحسب بشكل متكرر مضروب الرقم المحدد.

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

لذلك الأداء للجسم هو:يا(1) (ثابت).

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

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

ثم اجمع هذين معًا وسيكون لديك أداء الوظيفة العودية بأكملها:

1 * (ن-1) = يا(ن)


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

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

O((ن/2 + 1)*(ن/2)) = O(ن2/4 + ن/2) = يا(ن2/4) = يا(ن2)

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

يا (سجل ن) < يا (ن) < يا (ن سجل ن) < يا (ن2) < يا (نك) < يا (هن) < يا (ن!)

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

أداتك الأساسية هي مفهوم نقاط القرار والإنتروبيا الخاصة بها.إنتروبيا نقطة القرار هي متوسط ​​المعلومات التي ستقدمها لك.على سبيل المثال، إذا كان البرنامج يحتوي على نقطة قرار ذات فرعين، فإن إنتروبيا البرنامج هي مجموع احتمالية كل فرع مضروبًا في السجل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*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024*10 + 1023/1024* حوالي 0 = حوالي 0.01 بت.لقد تعلمت القليل جدا!القرار الثاني ليس أفضل بكثير.ولهذا السبب يكون البحث الخطي بطيئًا جدًا.في الواقع، إنه أمر هائل في عدد البتات التي تحتاج إلى تعلمها.

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

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

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

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

دعونا نبدأ من البداية.

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

  1. العمليات الحسابية (على سبيل المثال+ أو %).
  2. العمليات المنطقية (على سبيل المثال، &&).
  3. عمليات المقارنة (على سبيل المثال، <=).
  4. عمليات الوصول إلى الهيكل (على سبيل المثال.الفهرسة المصفوفة مثل [i] ، أو المؤشر المتورط مع-> المشغل).
  5. مهمة بسيطة مثل نسخ قيمة إلى متغير.
  6. استدعاء وظائف المكتبة (على سبيل المثال، scanf، printf).

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

  1. عبارات الإسناد التي لا تتضمن استدعاءات دالة في تعبيراتها.
  2. قراءة البيانات.
  3. اكتب عبارات لا تتطلب استدعاءات دالة لتقييم الوسائط.
  4. تنكسر عبارات القفز ، وتستمر ، goto ، وإرجاع التعبير ، حيث لا يحتوي التعبير على استدعاء وظيفة.

في C ، يتم تشكيل العديد من الحلقات من أجل تهيئة متغير فهرس لبعض القيمة وزيادة هذا المتغير بمقدار 1 في كل مرة حول الحلقة.ينتهي الحلقة عندما يصل الفهرس إلى بعض الحد.على سبيل المثال، للحلقة

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

يستخدم متغير الفهرس i.يزيدني بنسبة 1 في كل مرة حول الحلقة ، وتتوقف التكرارات عندما تصل إلى N - 1.

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

على سبيل المثال، تتكرر حلقة for ((n − 1) − 0)/1 = n − 1 times، نظرًا لأن 0 هي القيمة الأولية لـ i ، n - 1 هي أعلى قيمة تم الوصول إليها من قبل i (أي ، عندما تصل إلى N - 1 ، تتوقف الحلقة ولا يحدث التكرار مع i = n - 1) ، ويتم إضافة 1 إلى 1 أنا في كل تكرار للحلقة.

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


الآن فكر في هذا المثال:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

نحن نعرف ذلك خط 1) يأخذ O(1) وقت.من الواضح أننا نتجول في حلقة N Times ، حيث يمكننا تحديدها من خلال طرح الحد الأدنى من الحد الأعلى الموجود على السطر (1) ثم إضافة 1.نظرًا لأن الجسم ، السطر (2) ، يستغرق O (1) الوقت ، يمكننا إهمال الوقت للزيادة J والوقت لمقارنة J مع N ، وكلاهما هو أيضا O (1).وبالتالي فإن زمن تشغيل السطرين (1) و (2) هو حاصل ضرب n وO(1), ، الذي O(n).

وبالمثل ، يمكننا ربط وقت تشغيل الحلقة الخارجية التي تتكون من خطوط (2) إلى (4) ، وهو

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

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

التهيئة i = 0 من الحلقة الخارجية واختبار (n + 1) ST للحالة i <n تأخذ بالمثل (1) الوقت ويمكن إهمالها.أخيرًا ، نلاحظ أننا نتجول في الحلقة الخارجية في الأوقات ، ونستغرق وقتًا في كل تكرار ، وإعطاء المجموعO(n^2) وقت الركض.


مثال عملي أكثر.

enter image description here

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

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

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

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

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

لمزيد من المعلومات، تحقق من صفحة ويكيبيديا حول هذا الموضوع.

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

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

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

لذلك يمكننا الحد الأعلى من مقدار العمل بواسطة O(n*log(n)).

ومع ذلك، يخفي Big O بعض التفاصيل التي لا يمكننا تجاهلها في بعض الأحيان.فكر في حساب تسلسل فيبوناتشي باستخدام

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

ولنفترض فقط أن a وb هما BigIntegers في Java أو شيء يمكنه التعامل مع الأعداد الكبيرة بشكل تعسفي.قد يقول معظم الناس أن هذه خوارزمية O(n) دون أن تتوانى.السبب هو أن لديك n تكرارات في حلقة for وأن O(1) يعمل بجانب الحلقة.

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

1 + 2 + 3 + ...+ ن = ن(ن-1)/2 = أو(ن^2)

لذلك تعمل هذه الخوارزمية في زمن رباعي!

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

أعتقد أنها أقل فائدة بشكل عام، ولكن من أجل الاكتمال هناك أيضًا أوميغا الكبيرة Ω, ، والذي يحدد الحد الأدنى لتعقيد الخوارزمية، و ثيتا الكبيرة Θ, ، والذي يحدد كلا من الحد العلوي والسفلي.

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

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

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

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

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

كمثال بسيط جدًا، لنفترض أنك تريد إجراء فحص سلامة لسرعة فرز قائمة إطار عمل .NET.يمكنك كتابة شيء مثل ما يلي، ثم تحليل النتائج في برنامج 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);

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

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

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

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

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

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

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

سؤال عظيم!

تنصل:تحتوي هذه الإجابة على بيانات خاطئة، راجع التعليقات أدناه.

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

تحقق من هذا الموقع للحصول على تعريف رسمي جميل لـ Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) تعني أن هناك ثوابت موجبة c وk، بحيث يكون 0 ≥ f(n) ≥ cg(n) للجميع n ≥ k.يجب أن تكون قيم c و k ثابتة للدالة f ويجب ألا تعتمد على n.


حسنًا، ماذا نعني الآن بتعقيدات "أفضل الحالات" و"أسوأ الحالات"؟

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

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

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

لا أعرف كيفية حل هذه المشكلة برمجيًا، لكن أول شيء يفعله الأشخاص هو أخذ عينات من الخوارزمية لأنماط معينة في عدد العمليات المنجزة، على سبيل المثال 4n^2 + 2n + 1 لدينا قاعدتان:

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

إذا قمنا بتبسيط f(x)، حيث f(x) هي صيغة عدد العمليات التي تم إجراؤها، (4n^2 + 2n + 1 موضحة أعلاه)، فسنحصل على قيمة big-O [O(n^2) في هذا قضية].ولكن هذا يجب أن يأخذ في الاعتبار استيفاء لاغرانج في البرنامج، والذي قد يكون من الصعب تنفيذه.وماذا لو كانت قيمة O الكبيرة الحقيقية هي O(2^n)، وقد يكون لدينا شيء مثل O(x^n)، لذلك ربما لن تكون هذه الخوارزمية قابلة للبرمجة.ولكن إذا أثبت شخص ما أنني مخطئ، أعطني الرمز....

بالنسبة للكود A، سيتم تنفيذ الحلقة الخارجية لـ n+1 مرات، الوقت "1" يعني العملية التي تتحقق مما إذا كنت لا أزال أستوفي المتطلبات.وتعمل الحلقة الداخلية n مرات، n-2 مرات....هكذا،0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

بالنسبة للكود B، على الرغم من أن الحلقة الداخلية لن تتدخل وتنفذ الدالة foo()، سيتم تنفيذ الحلقة الداخلية لمدة n مرات تعتمد على وقت تنفيذ الحلقة الخارجية، وهو O(n)

أود أن أشرح Big-O في جانب مختلف قليلاً.

Big-O هو فقط لمقارنة مدى تعقيد البرامج مما يعني مدى سرعة نموها عندما تتزايد المدخلات وليس الوقت المحدد الذي يتم إنفاقه للقيام بالإجراء.

IMHO في صيغ big-O، من الأفضل عدم استخدام معادلات أكثر تعقيدًا (قد تلتزم فقط بالمعادلات الموجودة في الرسم البياني التالي.) ومع ذلك، لا يزال بإمكانك استخدام صيغ أخرى أكثر دقة (مثل 3^n، n^3، .. .) ولكن أكثر من ذلك قد يكون مضللاً في بعض الأحيان!لذا من الأفضل أن تبقي الأمر بسيطًا قدر الإمكان.

enter image description here

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

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top