فيديو: كيف تحسب تعقيد الفضاء؟
2024 مؤلف: Lynn Donovan | [email protected]. آخر تعديل: 2023-12-15 23:43
مساعد فضاء : هو المؤقت فضاء (باستثناء حجم الإدخال) التي تخصصها الخوارزمية لحل المشكلة ، فيما يتعلق بحجم الإدخال. تعقيد الفضاء يشمل كلا من المساعد فضاء و فضاء المستخدمة من قبل المدخلات. تعقيد الفضاء = حجم الإدخال + المساعد فضاء.
فقط هكذا ، ما هو تعقيد الفضاء بالمثال؟
تعقيد الفضاء هو مقياس لمقدار تخزين العمل الذي تحتاجه الخوارزمية. هذا يعني مقدار الذاكرة المطلوبة ، في أسوأ الحالات ، في أي نقطة في الخوارزمية. كما هو الحال مع الوقت تعقيد ، نحن مهتمون في الغالب بكيفية عمل فضاء تحتاج إلى النمو ، بعبارات كبيرة ، حيث ينمو الحجم N لمشكلة المدخلات.
علاوة على ذلك ، ما الخوارزمية التي لديها أعلى تعقيد في الفضاء؟ خوارزميات الفرز
| الخوارزمية | هيكل البيانات | تعقيد الفضاء: الأسوأ |
|---|---|---|
| فرز سريع | مجموعة مصفوفة | تشغيل) |
| دمج الفرز | مجموعة مصفوفة | تشغيل) |
| نوع كومة | مجموعة مصفوفة | يا (1) |
| فرز سلس | مجموعة مصفوفة | يا (1) |
الى جانب ذلك ، ما هو تعقيد الفضاء وتعقيد الوقت؟
تعقيد الوقت هي وظيفة تصف مقدار زمن تأخذ الخوارزمية من حيث كمية المدخلات إلى الخوارزمية. تعقيد الفضاء هي وظيفة تصف مقدار الذاكرة ( فضاء ) تأخذ الخوارزمية من حيث كمية المدخلات إلى الخوارزمية.
هل يشمل تعقيد الفضاء المدخلات؟
يشمل تعقيد الفضاء كلاهما مساعد فضاء و فضاء استعمل من قبل إدخال.
موصى به:
أي خوارزمية الفرز لديها أفضل تعقيد مقارب؟
نوع كومة وبالمثل ، ما هي خوارزمية الفرز التي تتمتع بأفضل وقت تشغيل؟ لأفضل حالة إدراج فرز و نوع كومة هي الأفضل حيث أن تعقيد وقت تشغيل الحالة الأفضل هو O (n). بالنسبة للحالة المتوسطة ، فإن أفضل تعقيد لوقت التشغيل المقارب هو O (nlogn) والذي يتم توفيره بواسطة Merge Sort ، نوع كومة ، فرز سريع.
كيف يتم حساب تعقيد فرز الدمج؟
2 إجابات. يستغرق تقسيم العقدة A [L، R] إلى عقدتين R & ناقص؛ L + 1 مرة ثم دمج العقدتين الفرعيتين A [L، M] و A [M + 1، R] مرة أخرى يأخذ A [R & minus؛ L +1] الوقت. وبالتالي ، بالنسبة لكل عقدة ، فإن عدد العمليات التي تنفذها الخوارزمية يساوي ضعف حجم المصفوفة المقابلة لتلك العقدة
ما مدى تعقيد خوارزمية ديكسترا؟
التعقيد الزمني لخوارزمية Dijkstra هو O (V 2) ولكن مع قائمة انتظار الأولوية الدنيا ، فإنه ينخفض إلى O (V + E l o g V)
ما هو مدى تعقيد خوارزمية فرز الكومة؟
فرز الكومة هو خوارزمية موضعية. تعقيد الوقت: التعقيد الزمني لـ heapify هو O (Logn). التعقيد الزمني لـ createAndBuildHeap () هو O (n) وتعقيد الوقت الإجمالي ل Heap Sort هو O (nLogn)
ما هي أسوأ حالة ومتوسط تعقيد الحالة لشجرة البحث الثنائية؟
خوارزمية شجرة البحث الثنائية متوسط أسوأ حالة المسافة O (n) O (n) البحث O (log n) O (n) أدخل O (log n) O (n) حذف O (log n) O (n)