وقت تشغيل عملية الاتحاد المحددة

Question

بالنظر إلى المجموعتين A وB، ما هي الخوارزمية الشائعة المستخدمة للعثور على اتحادهما، وما هو وقت تشغيلها؟

حدسي:

a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
    union.add(el)

for el in b:
    union.add(el)

قم بإضافة عمليات التحقق من التصادم، وهو O(1)، ثم قم بإضافة العنصر وهو (؟؟).يتم ذلك n مرات (حيث n هو |a| + |b|).إذن هذا هو O(n * x) حيث x هو متوسط ​​وقت التشغيل لعملية الإضافة.

هل هذا صحيح؟

Answer 1

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

http://en.wikipedia.org/wiki/Union_find

وانظر مثال التطبيق هنا

http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!220.entry

Answer 2

يعتمد تعقيد الإضافة/البحث (التصادم) على تنفيذ الاتحاد.

إذا كنت تستخدم بعض هياكل البيانات القائمة على التجزئة، فستكون عملية التصادم الخاصة بك ثابتة بالفعل بافتراض وجود وظيفة تجزئة جيدة.

بخلاف ذلك، من المحتمل أن تكون الإضافة هي O(Log(N)) لقائمة مصنفة/بنية بيانات شجرة.

Answer 3

الجواب الأول:إذا كنت تتعامل مع مجموعات من الأرقام, ، يمكنك تنفيذ مجموعة كـ a مرتبة ناقلات العناصر المتميزة.ثم يمكنك تنفيذ union(S1, S2) ببساطة كعملية دمج (التحقق من التكرارات)، والتي تستغرق وقت O(n)، حيث n = مجموع العناصر الأساسية.

الآن، إجابتي الأولى ساذجة بعض الشيء.وأكوسيتي على حق:يمكنك، ويجب عليك، تنفيذ مجموعة كجدول تجزئة (يجب أن تكون المجموعة حاوية عامة، ولا يمكن فرز جميع الكائنات!).بعد ذلك، يكون كل من البحث والإدراج O(1)، وكما خمنت، يستغرق الاتحاد وقتًا O(n).

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

Answer 4

إذا كان بإمكانك استخدام مجموعات البت (كل بت في مصفوفة int يساوي عنصرًا في مجموعتك)، فيمكنك ببساطة المرور فوق مصفوفة int وأو العناصر.هذا له التعقيد O(N) (حيث N هو طول المصفوفة) أو O((m+31)/32) حيث M هو عدد العناصر.