مقارنة الخوارزميات والهياكل抽象ية في الخوارزميات
| English | العربية |
|---|---|
| Big-O/bɪɡ əʊ/ | Big-O |
| time complexity/taɪm kəmˈpleksɪti/ | تعقيد الوقت |
| space complexity/speɪs kəmˈpleksɪti/ | تعقيد المساحة |
| depth-first/depθ fɜːst/ | أولوية العمق |
| breadth-first/bredθ fɜːst/ | أولوية العرض |
| binary tree/ˈbaɪnəri triː/ | شجرة ثنائية |
الخوارزمية التي ستبقى أطول من الكون
- يجب على بائع زيارة 25 مدينة والعودة إلى المنزل بأقصر طريق. جرب كل ترتيب وسيكون هناك حوالي $10^{23}$ منها. آلة تتحقق من مليار ترتيب في الثانية ستحتاج ثلاثة ملايين عام.
- أضف مدينة واحدة أخرى وسيتضاعف العمل بمقدار 25 مرة. هذا ليس حاسوبًا يحتاج إلى أن يكون أسرع؛ بل هو نهج لا يمكن أن يعمل أبدًا، بأي سرعة، على أي عتاد.
- معرفة ذلك قبل كتابة البرنامج هو ما تخدمه له تحليل التعقيد. إنه الفرق بين اختيار خوارزمية واكتشاف، بعد أشهر، أن خوارزميتك لا قابلة للتوسع.
- هذه الدرس هو Big-O للوقت والمساحة، وكيف تشكل الأنواع المجردة للبيانات (ADTs) الخوارزميات المبنية عليها.
تعقيد الوقت
- تعقيد الوقت يصف كيف ينمو وقت التشغيل مع حجم المدخلات $n$. يُكتب باستخدام رمز Big-O، الذي يحتفظ فقط بالحد السائد ويتجاهل الثوابت.
- $O(1)$ ثابت، لا يعتمد الوقت على $n$ على الإطلاق. $O(\log n)$ لوغاريتمي، كما في البحث الثنائي. $O(n)$ خطي، كما في البحث الخطي. $O(n \log n)$، الترتيبات الجيدة. $O(n^2)$ تربيعي، كما في ترتيب الفقاعات وترتيب الإدراج.
- سبب تجاهل الثوابت: أنها تُطغى عليها. قد تتفوق خوارزمية $O(n^2)$ على خوارزمية $O(n \log n)$ من أجل $n = 10$، ولكن عند $n = 10{,}000$ لا شيء من الثوابت يمكن أن ينقذها.
تتقاطع المنحنيات مرة واحدة، وبعد ذلك يحدد الترتيب كل شيء
كيف ينمو وقت التنفيذ مع n
ارفع n للأعلى وقارن المنحنيات: O(1) و O(log n) تظل مسطحة تقريبًا، O(n) ترتفع باستمرار، O(n²) تنفجر. ولهذا السبب تُستخدم Big-O — وليس ساعة إيقاف — للمقارنة بين الخوارزميات على المدخلات الكبيرة.
أي Big-O يصف البحث الثنائي؟
تقليص النطاق بنصفه في كل خطوة هو لوغاريتمي — O(log n).
أي Big-O يصف فرز الفقاعات في أسوأ حالة؟
حلقتان متداخلتان عبر n عنصر تعطيان O(n²).
طابق كل خوارزمية بتعقيدها الزمني.
البحث الخطي هو O(n)، البحث الثنائي O(log n)، فرز الفقاعات O(n²).
مثال محلول: ما الذي يفعله مضاعفة المدخلات
- يأخذ الخوارزمية 4 ثوانٍ على 1,000 عناصر. قدر وقتها على 2,000 عناصر إذا كانت $O(n)$، ثم إذا كانت $O(n^2)$.
- $O(n)$: مضاعفة $n$ تضاعف الوقت، لذا حوالي 8 ثوانٍ.
- $O(n^2)$: مضاعفة $n$ تربّع الوقت، لذا حوالي 16 ثانية. عند 10,000 عنصر ستكون 100 ضعف الأصلي، حوالي 400 ثانية.
- $O(\log n)$ سيضيف خطوة واحدة فقط، و**$O(1)$** لن يتغير على الإطلاق. استنتج من الترتيب، وليس من معادلة.
خوارزمية ذات تعقيد O(n squared) تأخذ 4 ثوانٍ على 1,000 عنصر. تقريبًا كم ثانية ستستغرق على 2,000؟
تضاعف n يربّع زمن خوارزمية O(n squared). نفس المضاعفة ستأخذ خوارزمية O(n) من 4 ثوانٍ إلى 8.
تعقيد المساحة
- تعقيد المساحة هو الذاكرة الإضافية التي تحتاجها الخوارزمية، oltre input itself.
- ترتيب الفقاعات وترتيب الإدراج يستخدمان $O(1)$ ذاكرة إضافية: يعملان محليًا، مما يتطلب المتغيرات القليلة فقط. استخدام دمج الترتيب $O(n)$، لأنه يبني مصفوفة ثانية.
- الاستخدام العودي يستخدم ذاكرة المكدس متناسبة مع عمقه، لأن كل استدعاء لم يكتمل يحتفظ بإطاره الخاص.
- غالبًا ما يكون هناك مفاضلة بين الوقت والذاكرة: تخزين النتائج لتجنب إعادة حسابها، كما تفعل الذاكرة المؤقتة، يشتري السرعة بالمساحة.
ما الذي يحدد الاختيار آخر
- Big-O يتعلق بـ النمو، وليس السرعة المطلقة. بالنسبة لـ $n$ صغير، يمكن لخوارزمية $O(n^2)$ بسيطة أن تتفوق على خوارزمية $O(n \log n)$ معقدة، ومن الأسهل كتابتها بشكل صحيح.
- الاستقرار مهم عندما تكون القائمة مرتبة بالفعل حسب مجال آخر. البساطة مهمة لأن الخوارزمية البسيطة تحتوي على أماكن أقل لإخفاء الأخطاء.
- الإجابة الصادقة عن "أي خوارزمية" غالبًا ما تذكر الترتيب و الظروف: هذه، لأن $n$ كبير والبيء arrives unsorted.
فرز "في الموقع":
الخوارزميات "في الموقع" (مثل فرز الفقاعات وإدراج الفرز) تقوم بالفرز داخل المصفوفة الأصلية، باستخدام مساحة إضافية ثابتة.
لماذا يكون تعقيد مساحة فرز الفقاعات O(1) حتى أنه يرتب مصفوفة بحجم n عنصر؟
إنه يرتب في الموقع. فرز الدمج هو O(n) لأنه يبني مصفوفة ثانية، والتكلفة العودية تعتمد على الذاكرة متناسبة مع عمقه.
ADTs داخل الخوارزميات
- الأنواع المجردة للبيانات من الموضوع 10 هي الآلية التي تُبنى عليها الخوارزميات، واختيار واحد منها يشكل الخوارزمية.
- المكدس يعطي البحث الأولوية العمقية: ادفع الجيران، وأخذ أحدثها، وينغمس البحث في مسار واحد قبل التراجع. recursion uses the call stack for exactly this.
- الطابور يعطي البحث الأولوية العرضية: أدخل الجيران في الطابور، وأقدمها، وينتشر البحث للخارج في حلقات، وهو ما يجد أقصر طريق في الرسم البياني غير الموزون.
- الشجرة الثنائية تحافظ على القيم مرتبة بحيث يستبعد البحث نصف العقد المتبقية في كل خطوة، مما يمنح البحث الثنائي $O(\log n)$ على بنية يمكن أيضًا أن تنمو.
أي العبارات عن Big-O صحيحة؟ حدد جميع ما ينطبق.
Big-O لا تقول شيئًا عن الثواني؛ بل هي تتعلق بالنمو. وهذا هو سبب وجود نقطة التقاطع مع خوارزمية أبسط عند أحجام صغيرة.
مثال محلول: نفس الرسم البياني، بحثان
- متاهة يتم استكشافها من مدخل واحد. قارن استخدام مكدس مع استخدام طابور.
- مع المكدس، يتم استكشاف المسار الذي تم العثور عليه مؤخرًا التالي، لذلك يذهب البحث عميقًا في مسار واحد حتى ينتهي، ثم يعود. يستخدم ذاكرة متناسبة مع عمق المسار.
- مع الطابور، يتم استكشاف المسار الذي تم العثور عليه قديمًا التالي، لذلك يفحص البحث كل شيء على بُعد خطوة واحدة، ثم كل شيء على بُعد خطوتين. يجد أقصر طريق أولاً، لكنه يحتفظ بكل موقع على المسافة الحالية في الذاكرة.
- سمِّ نوع البيانات المجرد، وسمِّ الترتيب الناتج للاستكشاف، وسمِّ النتيجة.
المكدس (LIFO) يقود بشكل طبيعي إلى استكشاف العمق، بينما الطابور (FIFO) يقود إلى استكشاف العرض.
الأداة abstract التي تختارها تحدد ترتيب البحث — المكدس يذهب عميقًا أولاً، والطابور يستكشف مستوى بمستوى.
طابق كل أداة abstract مع الاستكشاف الذي تنتجه وعاقبته.
الأحدث أولاً، أو الأقدم أولاً. هذا الاختيار الوحيد يحدد ما إذا كان البحث سيمضي عميقًا أو عريضًا.
علامات ضائعة
- Big-O يصف النمو مع حجم المدخلات، وليس الثواني. "إنه سريع" ليس إجابة عن التعقيد.
- مضاعفة المدخلات تضاعف وقت $O(n)$ وتربّع $O(n^2)$. استنتج من الترتيب.
- تعقيد المساحة هو الذاكرة الإضافية، ولهذا السبب يُعد ترتيب الموضع في $O(1)$ حتى لو كان حجم المصفوفة $n$.
- المكدس يعطي البحث العميق، والجدول يعطي البحث العريض. الحصول على هذه الأزواج بشكل صحيح هو جوهر عدد من الأسئلة.
لقد فهمت الأمر
- تعقيد الوقت في Big-O يصف النمو مع $n$: $O(1)$، $O(\log n)$، $O(n)$، $O(n \log n)$، $O(n^2)$؛ يتم تجاهل الثوابت لأنه على النطاق الكبير، الترتيب هو ما يحدد
- مضاعفة $n$ تضاعف $O(n)$ وتربع $O(n^2)$؛ نقطة التقاطع مع خوارزمية "أسوأ" لا توجد إلا لـ $n$ الصغيرة
- تعقيد المساحة هو الذاكرة الإضافية: الترتيبات الموضعية هي $O(1)$، ودمج الترتيب (merge sort) هو $O(n)$، والتراجع يتطلب عمق المكدس
- المكدس يعطي البحث العميق، والجدول يعطي البحث العريض، والشجرة الثنائية تقلل العقد المتبقية للنصف في كل خطوة