/Time Complexity Analysis – المقال الأول

Time Complexity Analysis – المقال الأول

هذا المقال – إن شاء الله – هو بداية لسلسة مقالات عن هياكل البيانات data structures، سنتعرف من خلالها على أنواع ال data structures المختلفة وخصائصها وطريقة تمثيلها في الذاكرة.
..لكن في البداية وتحديدًا في المقال ده سنتكلم باختصار عن مصطلح مهم ونحتاجه بكثرة في دراستنا لل data structures وهو التعقيد الزمني time complexity.

لنفرض أن لدينا خوارزميتين تقومان بنفس الوظيفة، الأولى تؤدي الوظيفة في خلال 3 ثوانٍ، بينما الثانية تستغرق 7 ثوانٍ لإتمامها فأيهما تفضل؟!
.. لا شك أن الجميع يتفق على أن الأولى هي الأفضل … لكن في الواقع أنا لا أستطيع اختيار الأفضل بينهما إلا عند توافر شرط مهم وهو أن تكون الظروف التي تعمل فيها الخوارزميتان متماثلة من حيث (سرعة الجهاز المستخدم – لغة البرمجة – ونوع ال compiler… وغيرها)، عندها فقط يمكن أن نختار الخوارزمية الأولى.

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

لنفترض أن لدينا جهاز يستغرق وحدة زمنية واحدة للقيام بالعمليات الحسابية والمنطقية والتخزين فعلى سبيل المثال:

c = a + b;

 

لتنفيذ هذا السطر سيستغرق الجهاز وحدة زمنية واحدة للجمع وأخرى لتخزين الناتج في المتغير c وهو وقت ثابت لا يتغير بتغير قيم a و b، والخوارزميات التي تستغرق وقتاً ثابتاً لا يتغير بتغير الدخل نعبر عن كفاءتها ب (1)O …

ماذا لو قمنا بتغيير بسيط على الكود ووضعناه داخل حلقة تكرارية ، تكرر نفسها n من المرات:

for (int i = 0; i < n; i++)
    c = a + b;

 

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

وفرضاً إذا حصلنا على معادلة بهذا الشكل c1*n2 + c2*n + c3 يتم التعبير عنها ب (O(n… وهكذا وكلما كانت قيمة المتغير داخل الأقواس أصغر كلما كانت الكفاءة أعلى.

Big-oh Notation

هذه الفقرة ستتناول ما يلي:
1. تعريف بسيط (غير دقيق) لل Big O notation
2. التعريف الرياضي لل Big O notaion (لن نقوم باستخدام رموز او عبارات رياضة معقدة)
3. كيفية حساب ال Big O طبقا للتعريف الرياضي
4. كيفية حساب ال Big O بطريقة سريعة و سهلة دون الحاجة للتفاصيل الرياضية المعقدة
5. أمثلة للفهم

1. التعريف البسيط لل Big O notaion:

عندما نقول ان خوارزمية ما لها كفاءة تمثل ب (O(expression فهذا يعني أن دالة وقت التنفيذ الخاص بهذه الخوارزمية تنتمي لمجموعة الدوال التي لها خرج أقل (وقت تنفيذ أقل) من أو يساوي وقت التنفيذ لل expression و ال expression هنا عبارة عن دالة أيضًا.

مثال(رقم المثال):
لنفترض أننا حددنا أن وقت التنفيذ لخوارمية ما يمثل بالعلاقة

f(n) = 4(n2) + 3n +2

إذا طبقنا مفهوم ال asymptotic notation علي هذه المعادلة نجد ان n2 هو الجزء المؤثر علي الوقت الذي تستغرقه الخوارزمية في التنفيذ وهذا التاثير سيظهر عند القيم الكبيرة لل n .. n في هذه الحالة هو حجم ال data الذي تتعامل معه الخوارزمية

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

إذًا كيف يمكن الحكم علي الخوارزمية السابقة إن كانت سيئة أو لا من خلال ال Big O؟
– لتحديد إذا ما كانت الخوارزمية ذات كفاءة عالية أو لا، ننظر إلى ما بين القوسين وهو n2 للمثال السابق .. ومن الواضح أنه عند القيم الكبيرة ل n فإن n2 سيكون كبيرًا جدًا .. بحيث أن n2 يمثل وقت التنفيذ
مما يعني أن وقت التنفيذ سيكون كبيرًا جدًا عند القيم الكبيرة لل n الذي قد يمثل حجم ال data التي تتعامل معها الخوارزمية

2. التعريف الرياضي لل Big O notaion:

لنفترض أننا حددنا كفاءة خوارزمية ما ب ((O(g(n ماذا يعني ذلك رياضيًا:
– يعني أن دالة وقت التنفيذ للخوارزمية تنتمي لمجموعة من الدوال .. بحيث أنه لكل دالة من هذه الدوال
ولنسمي أي دالة مثلاً (f(n يوجد ثابت وليكن c بحيث أن (g(n) *c > f(n وذلك عندما n >= n0

سنحاول توضيح هذا المفهوم يمثال:

لنفترض أن هناك خوارزمية ما تتعامل مع مجموعة من البيانات عددها n ولحساب ال big o تبعًا للمفهوم الرياضي نقوم بعمل الخطوات التالية:

1. حساب وقت تنفيذ الخوارزمية وتمثيلها كدالة في المتغير n

f(n) = 3 (n2) + 2 n + 2

2. تحديد العامل المؤثر بشكل كبير في زيادة قيمة الدالة .. في الدالة السابقة واضح أنه عند القيم الكبيرة ل n يكون n2 هو العامل المؤثر في الدالة

3. نحذف المتغيرات من المعادلة السابقة (في هذه الحالة المتغير n) ونقوم بضرب العامل المؤثر في كل الثوابت.. فإذا طبقنا ذلك علي المعادلة السابقة ينتج لنا المعادلة التالية

d(n) = 3 (n2) + 2 (n2) + n2 = 6 (n2)

4. واضح من المعادلتين أن (d(n) > f(n عندما يكون المتغير n >= 1

و هنا شكل توضيحي للمثال السابق:

 time complexity curve

وفي هذا الشكل يمكننا أن نرى أن الدالة (d(n تبدأ في الزيادة بشكل أسرع من الدالة (f(n وذلك عندما تصبح قيمه المتغير n >= 1

ويمكننا أن نري من هذا الشكل أن ال big O notation يحد الدالة من الأعلي .. لذلك يطلق على ال big O notation بأنه upper bound asymptotic notation.

إذًا يمكن القول أن الخوازمية السابقة تنفذ بكفاءة (O(6 * n2 .. ولكن ال big o notation هو عبارة عن asymptotic notation وذلك يعني أنه يجب حذف الثوابت لذلك كفاءة هذه الخوارزمية تصبح

O(n2)

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

حساب ال big O بشكل سهل و سريع:

الخطوات:
1. ننظر للمعادلة التي تمثل وقت تنفيذ الخوارزمية ولنسميها معادلة 1
2. نحاول إيجاد العامل المؤثر في وقت تنفيذ الخوارزمية وليكن هذا العامل A
3. تمثيل كفاءة الخوارزمية ب (O(A

فيما يلي شرح مثال لتوضيح المقصود من هذه الخطوات:

لنفترض أن وقت التنفيذ لخوارزمية مثلناه بالمعادلة التالية

f(n) = 5(n2) + 3 (n) + 2

بما أن n2 هو العامل المؤثر في وقت تنفيذ الخوارزمية إذًا يمكن القول بأن هذه الخوارزمية تنفذ بكفاءة (O(n2

وبذلك نعني أن وقت التنفيذ لهذه الخوارزمية لن يكون أعلي من c * nحيث c هنا هو ثابت إذًا تم ضربه في n2 يكون الناتج أعلى من الدالة (f(n

أمثلة:

في ما يلي مثالين لتوضيح كيف يمكن حساب زمن التنفيذ لكود معين وحساب ال Big O لهم

مثال1:

For (int i = 0; i < n; i++) 
    c=a+b;

 

كما ذكرنا سابقًا ..الزمن الذي يستغرقه المعالج للقيام بالجمع والتخزين ثابت ويتوقف على نوع المعالج
سنرمز للزمن الذي يستغرقه معالجنا الوهمي في تنفيذ c=a+b بالثابت c1 .. و يجب أن نضع في الاعتبار أن هناك وقت زائد في تهيئة قيمة عداد الحلقة وهذا الوقت ثابت أيضًا و لنفترضه c2

و بما أن c=a+b سيتم تنفيذها داخل الحلقة n من المرات إذًا زمن تنفيذ الكود السابق يمكن تمثيله بالمعادلة التالية

f(n) = c1 * n + c2

بما أن المعادلة السابقة قيمتها تزداد بزيادة قيمة المتغير n إذًا هو العامل المؤثر في المعادلة وبحذف الثوابت يمكن القول بأن هذا الكود يتم تنفيذه بكفاءة (O(n

مثال 2:

For (int j = 0; j &lt; n; j++) //loop 1
{
    For (int i = 0; i &lt; n; i++)
        c = a + b; //loop2
}

 

مثل المثال السابق كود الحلقة الثانية سيتم تنفيذه في زمن يمثل ب

C1 * n + c2

ولكن هذا الكود يتم تنفيذه داخل حلقة أخري n من المرات .. إذًا بضرب n في المعادلة السابقة وجمع الثابت c3 الذي يمثل زمن تهيئة العداد للحلقة 1.. نحصل على المعادلة التالية التي تمثل زمن التنفيذ الكلي للكود السابق

f(n) = c1 (n 2) + c2 n + c3

واضح أنه عند القيم الكبيرة جدًا ل n .. فإن n2 تكون هي العامل المؤثر في قيمة المعادلة، إذًا بإهمال الثوابت والجزء c2 n +c3 الذي سيصبح مهمل القيمة عند القيم الكبيرة ل n

و بذلك يمكننا القول أن الكود السابق يتم تنفيذه بكفاءة (O(n2

هنا نكون قد وصلنا لنهاية المقال ويجب أن ننوه بأنه توجد أنواع أخري لل asymptotic notation مثل ال Big-theta وال Big-omega لم نتتطرق للحديث عنها لأننا لن نستخدمها في هذه السلسلة وإذًا كنت مهتمًا يمكنك البحث عنها

إذًا كان هذا كل شئ لهذا المقال .. في المقال القادم بإذن الله سنتحدث عن ال arrays وال linked lists

فتابعونا (: