التعقيد الزمني (Time Complexity)

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

لا نقيسه بالثواني، بل نقيسه بعدد الخطوات التي تزداد عند زيادة حجم المدخلات.

التعقيد الزمني يساعدك على مقارنة الخوارزميات بدون تشغيلها فعليًا.

لنفترض أن لدينا هذا الكود:

for (int i = 0; i < n; i++)
    cout << i << " ";

إذا كان \(n = 10\)، يطبع 10 أرقام. إذا كان \(n = 1000\)، يطبع 1000 رقم. إذا تضاعف \(n\)، فإن عدد الخطوات أيضًا يتضاعف.

نقول إن هذا الكود يعمل في \(O(n)\) زمن، لأنه يحتوي على \(n\) خطوة/عملية. هذا يعني أن الوقت ينمو خطيًا مع حجم المدخلات.

ما معنى \(O(\ldots)\)

الرمز الكبير \(O\) (Big O) يوضح كيف ينمو عدد الخطوات مع زيادة \(n\).

نهتم فقط بالنمو الرئيسي، وليس بالثوابت أو التفاصيل الصغيرة.

الاسم	المثال	الوصف
\(O(1)\)	`x = a + b;`	وقت ثابت – يعمل فورًا بغض النظر عن حجم n
\(O(\log n)\)	`set::insert`	كل خطوة تقلل المشكلة للنصف
\(O(n)\)	حلقة على مصفوفة	الوقت ينمو خطيًا
\(O(n \log n)\)	ترتيب	أبطأ قليلًا من \(O(n)\)، ولكن أسرع بكثير من \(O(n^2)\)
\(O(n^2)\)	حلقات متداخلة	الوقت ينمو بسرعة كبيرة عند زيادة n
\(O(2^n)\)	تجربة جميع التركيبات	أسي – ينمو بشكل هائل بسرعة

كلما كان التعقيد أصغر، كان النمو أسرع.

وقت ثابت – \(O(1)\)

زيادة الرقم

معطى لك رقم \(x\). قم بزيادة \(x\) بمقدار 1، ثم اطبعه.

Solution

#include <iostream>

using namespace std;

int main(){
    int x;
    cin >> x;

    x += 1;

    cout << x << '\n';
}

هنا، قمنا بثلاثة أشياء:

قراءة عدد صحيح من المدخلات
زيادة العدد بمقدار واحد
إخراج العدد

كلها عمليات بسيطة. لكننا لا نقول إن هذا تعقيد \(O(3)\)، لأننا لا نهتم بالثوابت؛ نهتم فقط بالنمو الرئيسي. إذن هذا \(O(1)\).

وقت خطي – \(O(n)\)

مجموع المال

معطى لك \(n\) أوراق نقدية قيمتها \(arr[0]\) ريال، \(arr[1]\) ريال، …، \(arr[n-1]\) ريال. كم مجموع الريالات لديك؟

Solution

#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;

    int arr[n];

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];

    cout << sum << '\n';
}

الحلقة تعمل مرة لكل عنصر. إذا تضاعفت المصفوفة، يتضاعف الوقت أيضًا.

لاحظ أننا أنشأنا مصفوفة وأدخلنا العناصر؛ هذا يأخذ عمليتين لكل عنصر. أيضًا نقرأ عدد العناصر، نضبط المتغير \(sum\) على صفر، وفي النهاية نطبع sum. بالمجموع: \(1 + n + n + 1 + n + 1 = 3n + 3\). لكننا لا نهتم بالثوابت، إذن التعقيد \(O(3n+3) = O(n)\) - خوارزمية زمنها خطي.

وقت تربيعي – \(O(n^2)\)

النسخ

معطى لك \(n\) أوراق نقدية قيمتها \(arr[0]\) ريال، \(arr[1]\) ريال، …، \(arr[n-1]\) ريال. لكل من \(n\) أيام، قم بزيادة قيمة كل ورقة بمقدار واحد. بعد اليوم الأول، تصبح الأوراق: \(arr[0]+1\), \(arr[1]+1\), …، \(arr[n-1]+1\). بعد اليوم الثاني: \(arr[0]+2\), … وهكذا. بعد \(n\) أيام ستكون الأوراق: \(arr[0]+n\), …، \(arr[n-1]+n\).

اطبع قيم كل الأوراق لكل يوم من الأيام \(n\).

#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    for (int days = 1; days <= n; days++){
        for (int i = 0; i < n; i++){
            cout << arr[i] + days << ' ';
        }
        cout << '\n';
    }
}

هناك \(n\) أيام و \(n\) أوراق في كل يوم يجب زيادتها. بالمجموع، نقوم بـ \(O(n^2)\) عملية (مع تجاهل الثوابت). إذا كان \(n = 10\)، فإن الخطوات = 100. إذا كان \(n = 1000\)، فإن الخطوات = مليون.

لهذا يمكن أن تصبح الخوارزميات \(O(n^2)\) بطيئة جدًا بسرعة.

مقارنة معدلات النمو

لنرى كيف تنمو مع زيادة n:

\(n\)	\(O(1)\)	\(O(\log n)\)	\(O(n)\)	\(O(n^2)\)
10	1	3	10	100
100	1	7	100	10,000
1000	1	10	1000	1,000,000

حتى لو بدت الفروقات صغيرة عند n صغير، فإنها تتضخم جدًا عند n كبير.

قاعدة سريعة

\(n\)	التعقيد الأقصى المقبول
\(\leq 10\)	\(O(n!)\)
\(\leq 20\)	عادة \(O(2^n)\) مقبول
\(\leq 1000\)	عادة \(O(n^2)\) مقبول
\(\leq 10^5\)	\(O(n \log n)\) أو أفضل
\(\leq 10^7\)	\(O(n)\) أو أفضل
\(\geq 10^9\)	فقط \(O(1)\) أو \(O(\log n)\)

هذا يساعدك على تخمين نوع الحل المناسب لحجم مدخلات معين.

تحسين الحلول

أحيانًا ليس واضحًا، لكن يمكنك جعل البرنامج أسرع بالتفكير في حلول أذكى.

المجموع البسيط

معطى لك رقم \(n\). أوجد مجموع: \(-n + (-n+1) + (-n+2) + ... + -1 + 0 + 1 + ... + (n-2) + (n-1) + n\).

Solution

حل بسيط خطيًا يكون هكذا:

#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;

    long long sum = 0;
    for (int i = -n; i <= n; i++)
        sum += i;

    cout << sum << '\n';
}

هذا الحل خطي زمنه \(O(n)\).

Solution

يمكننا عمل أفضل من ذلك. كل عدد يظهر مرة موجبة ومرة سالبة – \(+n\) و \(-n\). إذن في النهاية، كل الأعداد تلغي بعضها البعض ويبقى فقط صفر. الحل الأبسط:

#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;

    cout << 0 << '\n';
}

هذا الحل \(O(1)\)، وقت ثابت وأسرع بكثير من الحل البسيط. دائمًا حاول التفكير في أسرع حل ممكن.

التعقيد المكاني (Space complexity)

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

مثال:

int arr[n];  // مساحة O(n)
int x;       // مساحة O(1)