حساب تعقيد الخوارزمية

contents

• how do we calculate the complexity of algorithms
• the basic rule for calculating complexity of algorithm

كيف نحسب تعقيد الخوارزميات

في أي برنامج، العمليات الحسابية الأساسية مثل الجمع (+) والطرح (-) ، الضرب (*) ،القسمة (/) وإسناد القيم للمتغيرات (=) كل هذه العمليات تستغرق خطوة واحدة فقط للتنفيذ بمعنى آخر، تعقيد هذه العمليات ثابت .لتمثيل الوقت الثابت، نستخدم الرمز C.وكمثال لدينا البحث عن قيمة داخل مصفوفة فلنفترض أن لدينا برنامج بسيط للبحث عن قيمة X داخل مصفوفة، عندها إذا وجدت القيمة X، سيطبع البرنامج عبارة وجدته، وإذا لم تكن موجودة، سيطبع القيمة غير موجوددة. لتحليل تعقيد هذا البرنامج  نقوم بالتالي إسناد النصوص إلى المتغيرات يتم تنفيذه مرة واحدة فقط، لذلك تعقيده ثابت (C0). والشرط (if block) يتم تنفيذه مرة واحدة فقط، لذلك تعقيده ثابت (C1). أي عملية أخرى داخل الحلقة (for loop) يتم تنفيذها بعدد مرات تنفيذ الحلقة. إذا كانت الحلقة for تعمل N مرة، فهذا يعني أن التعليمات داخلها ستنفذ N مرة أيضًا. إذا كان لدينا 10 عناصر في المصفوفة، فسيتم تنفيذ العمليات 10 مرات. إذا كان لدينا 1000 عنصر، فسيتم تنفيذ العمليات 1000 مرة. وبالتالي، تعقيد هذا البرنامج هو O(N).

القاعدة الأساسية لحساب تعقيد خوارزمية

إذا كان هناك حلقة واحدة عندها التعقيد هو O(N). وإذا كان هناك حلقتان متداخلتان فالتعقيد هو O(N²). بينما إذا كان هناك 3 حلقات متداخلة فالتعقيد هو O(N³)، وهكذا.