مقارنة هياكل البيانات

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة

هذه مقارنة لأداء هياكل البيانات البارزة ، وذلك بقياس مدى تعقيد عملياتها المنطقية. للاطلاع على قائمة أكثر شمولاً لهياكل البيانات، انظر قائمة هياكل البيانات .

تُصنَّف المقارنات في هذه المقالة حسب نوع البيانات المجردة . ونظرًا لإمكانية استخدام بنية بيانات ملموسة واحدة لتنفيذ العديد من أنواع البيانات المجردة، فقد تظهر بعض بنى البيانات في مقارنات متعددة (على سبيل المثال، يمكن استخدام خريطة التجزئة لتنفيذ مصفوفة ترابطية أو مجموعة ).

القوائم

القائمة أو المتسلسلة هي نوع بيانات مجرد يمثل عددًا محدودًا من القيم المرتبة ، حيث قد تتكرر القيمة نفسها أكثر من مرة. تدعم القوائم عمومًا العمليات التالية :

  • نظرة خاطفة : الوصول إلى العنصر عند فهرس معين.
  • إدراج : إدراج عنصر جديد في فهرس معين. عندما يكون الفهرس صفرًا، يُسمى ذلك إضافة في البداية ؛ وعندما يكون الفهرس هو الفهرس الأخير في القائمة، يُسمى ذلك إضافة في النهاية .
  • حذف : إزالة العنصر الموجود في فهرس معين.
مقارنة هياكل بيانات القوائم
نظرة خاطفة (فهرس)قم بالتعديل (الإدراج أو الحذف) في …مساحة زائدة، متوسط
بدايةنهايةوسط
قائمة مرتبطةΘ( n )Θ(1)Θ(1)، العنصر النهائي المعروف؛ Θ( n )، عنصر نهائي غير معروفΘ( n )Θ( n )
المصفوفةΘ(1)غير متوفرغير متوفرغير متوفر0
مصفوفة ديناميكيةΘ(1)Θ( n )Θ(1) المستهلكةΘ( n )Θ( n ) [ 1 ]
شجرة متوازنةΘ(log n)Θ(log n)Θ(log n )Θ(log n )Θ( n )
قائمة الوصول العشوائيΘ(log n) [ 2 ]Θ(1)غير متوفر [ 2 ]غير متوفر [ 2 ]Θ( n )
شجرة المصفوفة المجزأةΘ(1)Θ( n )Θ(1) المستهلكةΘ( n )Θ(√ n )

خرائط

تخزن الخرائط مجموعة من أزواج (المفتاح، القيمة)، بحيث يظهر كل مفتاح ممكن مرة واحدة على الأكثر في المجموعة. وهي تدعم عمومًا ثلاث عمليات: [ 3 ]

  • إدراج : إضافة زوج (مفتاح، قيمة) جديد إلى المجموعة، مع ربط المفتاح بقيمته الجديدة. يتم استبدال أي ربط موجود. وسيطات هذه العملية هي المفتاح والقيمة.
  • حذف : إزالة زوج (مفتاح، قيمة) من المجموعة، وفصل المفتاح المحدد عن قيمته. وسيط هذه العملية هو المفتاح.
  • البحث : إيجاد القيمة (إن وجدت) المرتبطة بمفتاح معين. وسيط هذه العملية هو المفتاح، والقيمة هي القيمة المُعادة من العملية.

ما لم يُذكر خلاف ذلك، فإن جميع هياكل البيانات في هذا الجدول تتطلب مساحة O( n ).

بنية البياناتالبحث والإزالةالإدخالتم الطلب
متوسطأسوأ الحالاتمتوسطأسوأ الحالات
قائمة الجمعياتعلى )​على )​O(1)O(1)لا
شجرة B [ 4 ]O(log n )O(log n )O(log n )O(log n )نعم
جدول التجزئةO(1)على )​O(1)على )​لا
شجرة بحث ثنائية غير متوازنةO(log n )على )​O(log n )على )​نعم

مفاتيح عددية صحيحة

تُقدّم بعض هياكل بيانات الخرائط أداءً فائقًا في حالة المفاتيح العددية . في الجدول التالي، لنفترض أن m هو عدد البتات في المفاتيح.

بنية البياناتالبحث والإزالةالإدخالفضاء
متوسطأسوأ الحالاتمتوسطأسوأ الحالات
شجرة الاندماج[ ؟ ]O(log m n )[ ؟ ][ ؟ ]على )​
شجرة فان إمده بواسO(log log m )O(log log m )O(log log m )O(log log m )O( m )
تجربة سريعة للغايةO( n log m ) [ a ][ ؟ ]O(log log m )O(log log m )O( n log m )
تجربة سريعةO(log log m ) [ a ][ ؟ ]O(log log m ) [ a ][ ؟ ]على )​

قوائم الانتظار ذات الأولوية

قائمة الانتظار ذات الأولوية هي نوع بيانات مجرد يشبه قائمة الانتظار العادية أو المكدس . لكل عنصر في قائمة الانتظار ذات الأولوية أولوية مرتبطة به. في قائمة الانتظار ذات الأولوية، تُخدَم العناصر ذات الأولوية العالية قبل العناصر ذات الأولوية المنخفضة. تدعم قوائم الانتظار ذات الأولوية العمليات التالية:

  • إدراج : إضافة عنصر إلى قائمة الانتظار مع تحديد أولوية مرتبطة به.
  • find-max : إرجاع العنصر ذي الأولوية الأعلى من قائمة الانتظار.
  • حذف-الحد الأقصى : إزالة العنصر ذي الأولوية الأعلى من قائمة الانتظار.

يتم تنفيذ قوائم الانتظار ذات الأولوية بشكل متكرر باستخدام الأكوام .

أكوام

الكومة (القصوى) هي بنية بيانات قائمة على الشجرة تحقق خاصية الكومة : لأي عقدة معينة C، إذا كانت P عقدة أصلية لـ C، فإن مفتاح ( قيمة ) P أكبر من أو يساوي مفتاح C.

بالإضافة إلى عمليات قائمة الانتظار ذات الأولوية المجردة، يسرد الجدول التالي تعقيد عمليتين منطقيتين إضافيتين:

  • زيادة المفتاح : تحديث مفتاح.
  • الدمج : ضم كومتين لتشكيل كومة جديدة صالحة تحتوي على جميع عناصر كليهما، مما يؤدي إلى تدمير الكومتين الأصليتين.

فيما يلي تعقيدات زمنية [ 5 ] لهياكل بيانات الكومة المختلفة. يشير الاختصار am. إلى أن التعقيد المذكور هو التعقيد المُستهلك، وإلا فهو تعقيد أسوأ حالة. لمعرفة معنى " O ( f )" و" Θ ( f )"، راجع ترميز Big O. تفترض أسماء العمليات وجود كومة قصوى.

عمليةإيجاد الحد الأقصىحذف الحد الأقصىمفتاح الزيادةأدخلاندماجmake-heap [ b ]
ثنائي [ 5 ]Θ (1)Θ (log n ) Θ (log n ) Θ (log n ) Θ ( n )Θ ( n )
الانحراف [ 6 ]Θ (1)O (log n ) am. O (log n ) am. O (log n ) am. O (log n ) am. Θ ( n ) am.
يساري [ 7 ]Θ (1)Θ (log n ) Θ (log n ) Θ (log n ) Θ (log n ) Θ ( n )
ذات الحدين [ 5 ] [ 9 ]Θ (1)Θ (log n ) Θ (log n ) Θ (1) صباحًا.Θ (log n ) [ c ] Θ ( n )
التوزيع الثنائي المائل [ 10 ]Θ (1)Θ (log n ) Θ (log n ) Θ (1)Θ (log n ) [ c ] Θ ( n )
2-3 كومة [ 12 ]Θ (1)O (log n ) am. Θ (1)Θ (1) صباحًا.O (log n ) [ c ] Θ ( n )
الانحراف من الأسفل إلى الأعلى [ 6 ]Θ (1)O (log n ) am. O (log n ) am. Θ (1) صباحًا.Θ (1) صباحًا.Θ ( n ) am.
الاقتران [ 13 ]Θ (1)O (log n ) am. o (log n ) am. [ d ] Θ (1)Θ (1)Θ ( n )
الاقتران بالرتب [ 16 ]Θ (1)O (log n ) am. Θ (1) صباحًا.Θ (1)Θ (1)Θ ( n )
فيبوناتشي [ 5 ] [ 17 ]Θ (1)O (log n ) am. Θ (1) صباحًا.Θ (1)Θ (1)Θ ( n )
فيبوناتشي الصارم [ 18 ] [ e ]Θ (1)Θ (log n ) Θ (1)Θ (1)Θ (1)Θ ( n )
برودال [ 19 ] [ هـ ]Θ (1)Θ (log n ) Θ (1)Θ (1)Θ (1)Θ ( n ) [ 20 ]
  1. 1 2 3 الوقت المستهلك.
  2. ↑ عملية بناء الكومة هي عملية إنشاء كومة من سلسلة من n عنصرًا غير مُرتبة. يمكن إنجازها فيزمن Θ ( n ) بينما تعمل خوارزمية دمج العناصر في زمن O (log n ) (حيث يمكن توزيع كلا التعقيدين). [ 6 ] [ 7 ] وتحقق خوارزمية أخرى زمن Θ ( n ) للكومات الثنائية. [ 8 ] 
  3. بالنسبة للأكوام المستمرة (التي لا تدعم زيادة المفتاح )، يُقلل تحويل عام تكلفة دمج البيانات إلى تكلفة إدراجها ، بينما تكون التكلفة الجديدة لحذف القيمة القصوى هي مجموع التكاليف القديمة لكل من حذف القيمة القصوى ودمج البيانات . [ 11 ] هنا، يجعل هذا التحويل دمج البيانات يعمل في زمن Θ (1) (مُستهلك، إذا كانت تكلفة الإدراج كذلك) ، بينما لا يزال حذف القيمة القصوى يعمل في زمن O ( log n ). عند تطبيقه على أكوام ذات توزيع ثنائي منحرف، ينتج عنه طوابير برودال-أوكاساكي، وهي أكوام مستمرة ذات تعقيدات مثلى في أسوأ الحالات. [ 10 ] 
  4. ↑ الحد الأدنى لـΩ(سجل⁡سجل⁡ن)،{\displaystyle \Omega (\log \log n),}[ 14 ] الحد الأعلى لـيا(22سجل⁡سجل⁡ن).{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}[ 15 ]
  5. تُحقق طوابير برودال وأكوام فيبوناتشي الصارمة أفضل تعقيد في أسوأ الحالات للأكوام. وقد وُصفت في البداية بأنها هياكل بيانات إجرائية. أما طابور برودال-أوكاساكي فهو هيكل بيانات مستمر يحقق نفس المستوى الأمثل، باستثناء أنهلا يدعم زيادة المفتاح .

ملحوظات

  1. ↑ برودنيك، أندريه؛ كارلسون، سفانتي؛ سيدجويك، روبرت ؛ مونرو، جي آي؛ ديمين، إي دي (1999)، المصفوفات القابلة لتغيير الحجم في الوقت والمساحة الأمثلين (تقرير فني CS-99-09) (PDF) ، قسم علوم الحاسوب، جامعة واترلو
  2. 1 2 3 كريس أوكازاكي (1995). "قوائم الوصول العشوائي الوظيفية البحتة". وقائع المؤتمر الدولي السابع حول لغات البرمجة الوظيفية وهندسة الحاسوب : 86-95 . doi : 10.1145/224164.224187 .
  3. ↑ ميلهورن، كورت ؛ ساندرز، بيتر (2008)، "4 جداول التجزئة والمصفوفات الترابطية"، الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية (ملف PDF) ، سبرينغر، الصفحات 81-98 ، مؤرشف (ملف PDF) من الأصل بتاريخ 2014-08-02 
  4. ^ كورمين وآخرون. 2022 ، ص. 484.
  5. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  6. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  7. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  8. ↑ هايوارد، رايان؛ ماكديارميد، كولين (1991). "تحليل الحالة المتوسطة لبناء الكومة عن طريق الإدخال المتكرر" (ملف PDF) . مجلة الخوارزميات . 12 : 126-153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . مؤرشف من الأصل (ملف PDF) بتاريخ 2016-02-05 . تم الاطلاع عليه بتاريخ 2016-01-28 . 
  9. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30-09-2019 .
  10. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  11. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  12. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  13. ↑ إياكونو، جون (2000)، "تحسين الحدود العليا لأكوام الاقتران"، وقائع ورشة العمل الإسكندنافية السابعة حول نظرية الخوارزميات (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1851، دار نشر سبرينغر، الصفحات 63-77 ، arXiv : 1110.4428 ، CiteSeerX 10.1.1.748.7812 ، doi : 10.1007/3-540-44985-X_5 ، ISBN    3-540-67690-2
  14. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  15. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  16. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  17. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  18. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  19. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  20. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.

مراجع

  • كورمين، توماس H.؛ ليسرسون، تشارلز E.؛ ريفست، رونالد L.؛ شتاين ، كليفورد (2022/04/05). مقدمة للخوارزميات، الطبعة الرابعة مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 978-0-262-36750-9.