ترتيب التعقيد هو مصطلح يستخدم في علوم الكمبيوتر لقياس كفاءة الخوارزمية أو البرنامج. ويشير إلى مقدار الوقت والموارد اللازمة لحل مشكلة أو أداء مهمة. في البرمجة، عادة ما يتم التعبير عن ترتيب التعقيد من حيث كبير يا التدوين، الذي يعطي حدًا أعلى لمتطلبات الوقت أو المساحة للخوارزمية. سنتناول في هذا المقال ترتيب التعقيد في لغة البرمجة C وأهميته.
ترتيب التعقيد في لغة البرمجة C:
في برمجة C، يعتمد ترتيب تعقيد الخوارزمية على عدد العمليات التي يقوم بها البرنامج. على سبيل المثال، إذا كان لدينا مصفوفة بالحجم n ونريد البحث عن عنصر معين في المصفوفة، فإن ترتيب تعقيد الخوارزمية سيعتمد على عدد العناصر في المصفوفة. إذا قمنا بإجراء البحث الخطي من خلال مجموعة، سيكون ترتيب التعقيد على) مما يعني أن الوقت المستغرق للبحث عن العنصر سيزداد خطيًا مع حجم المصفوفة. إذا استخدمنا أ خوارزمية البحث الثنائية بدلا من ذلك، سيكون ترتيب التعقيد يا(سجل ن) مما يعني أن الوقت المستغرق للبحث عن العنصر سيزداد لوغاريتميًا مع حجم المصفوفة.
وبالمثل، فإن ترتيب التعقيد للخوارزميات الأخرى، مثل خوارزميات الفرز , خوارزميات الرسم البياني ، و خوارزميات البرمجة الديناميكية ويعتمد أيضًا على عدد العمليات التي يقوم بها البرنامج. يمكن التعبير عن ترتيب تعقيد هذه الخوارزميات باستخدام كبير يا الرموز.
جدول الحقيقة الكامل للمضيف
دعونا نلقي نظرة على بعض أوامر التعقيد الشائعة والخوارزميات المقابلة لها:
وهذا يعني أن الخوارزمية تستغرق مقدارًا ثابتًا من الوقت، بغض النظر عن حجم الإدخال. على سبيل المثال، يستغرق الوصول إلى عنصر في مصفوفة يا(1) الوقت، حيث يمكن الوصول إلى العنصر مباشرة باستخدام الفهرس الخاص به.
وهذا يعني أن الوقت الذي تستغرقه الخوارزمية يزداد لوغاريتميًا مع حجم الإدخال. وهذا يظهر بشكل شائع في خوارزميات فرق تسد يحب بحث ثنائي ، والتي تقسم المدخلات إلى أجزاء أصغر لحل المشكلة.
وهذا يعني أن الوقت الذي تستغرقه الخوارزمية يزداد خطيًا مع حجم الإدخال. ومن أمثلة هذه الخوارزميات البحث الخطي و فقاعة الفرز .
وهذا يعني أن الوقت المستغرق للخوارزمية يزيد بمقدار n مضروبًا في لوغاريتم n. ومن أمثلة هذه الخوارزميات فرز سريع و فرز الدمج .
وهذا يعني أن الوقت الذي تستغرقه الخوارزمية يزداد بشكل تربيعي مع حجم الإدخال. ومن أمثلة هذه الخوارزميات فقاعة الفرز و ترتيب بالإدراج .
سلسلة.مقارنة مع ج #
وهذا يعني أن الوقت الذي تستغرقه الخوارزمية يتضاعف مع كل زيادة في حجم الإدخال. وهذا يظهر بشكل شائع في الخوارزميات العودية مثل ال سلسلة فيبوناتشي .
من المهم أن تعرف أن ترتيب التعقيد يوفر فقط حدًا أعلى للوقت الذي تستغرقه الخوارزمية. قد يكون الوقت الفعلي المستغرق أقل بكثير من هذا الحد، اعتمادًا على البيانات المدخلة وتنفيذ الخوارزمية.
في برمجة C، يمكن تحديد ترتيب تعقيد الخوارزمية من خلال تحليل الكود وحساب عدد العمليات المنفذة. على سبيل المثال، إذا كانت لدينا حلقة تتكرر عبر مصفوفة بحجم n، فسيكون التعقيد الزمني للحلقة هو على) . وبالمثل، إذا كانت لدينا دالة عودية تطلق على نفسها اسم k times، فسيكون التعقيد الزمني للدالة يا (2 ^ ك) .
لتحسين أداء البرنامج، من المهم اختيار خوارزميات ذات ترتيب أقل من التعقيد. على سبيل المثال، إذا أردنا فرز مصفوفة، فيجب علينا استخدام خوارزمية فرز ذات ترتيب أقل من التعقيد، مثل: فرز سريع أو فرز الدمج ، بدلا من فقاعة الفرز ، والتي لديها ترتيب أعلى من التعقيد.
تحليل ترتيب التعقيد:
لتحليل ترتيب تعقيد الخوارزمية، نحتاج إلى تحديد كيفية نمو وقت التشغيل أو استخدام المساحة مع زيادة حجم الإدخال. الطريقة الأكثر شيوعًا للقيام بذلك هي حساب عدد العمليات الأساسية التي تقوم بها الخوارزمية.
شجرة ثنائية مقابل BST
العملية الأساسية هي عملية تستغرق وقتًا ثابتًا لتنفيذها، مثل إضافة رقمين أو الوصول إلى عنصر مصفوفة. من خلال حساب عدد العمليات الأساسية التي تقوم بها الخوارزمية كدالة لحجم الإدخال، يمكننا تحديد ترتيب التعقيد الخاص بها.
على سبيل المثال، خذ بعين الاعتبار دالة C التالية التي تحسب مجموع الأعداد الصحيحة n الأولى:
رمز ج:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>