تمرين التعقيد الحسابي

Question

أنا أقرأ "هياكل البيانات والخوارزميات" من Aho وHopcroft & Ullman، وأنا في حيرة من أمري مع التمرين 1.12 ب:

ما هو التعقيد الحسابي (المعبر عنه بترميز Big O) لإجراء باسكال هذا؟

procedure mysterious( n: integer );
    var
        i, j, k: integer;
    begin
        for i := 1 to n - 1 do
             for j := i + 1 to n do
                 for k := 1 to j do
                    {mysterious statement of O(1)}
    end

هلاّ ساعدتني من فضلك؟

شكرًا!

Answer 1

انها فوق³).يُظهر الحرف الكبير O كيف يتناسب وقت التنفيذ (أو الذاكرة أو أي شيء آخر) مع حجم المهمة (تم حذف معامل التناسب).

في هذه الحالات يتم تنفيذ البيان الداخلي مرات تتناسب مع (ن³).i يمتد من 1 إلى (n-1) - لذلك يتم تنفيذ كل شيء داخل الدورة الخارجية (n-1) مرات.يعمل j في المتوسط ​​من (n/2) إلى (n) - لذلك يتم تنفيذ كل شيء بالداخل (n-1)* (n/2) مرات.k يمتد في المتوسط ​​من 1 إلى (3/4*n).يؤدي هذا إلى تنفيذ (n-1)* (n/2)* (3/4*n-1) للبيان الداخلي.هذا هو (ن³).