كل فئة تعقيد ترسم منحنى
رسم التكلفة مقابل حجم الإدخال
ضع حجم الإدخال N على المحور السيني. ضع التكلفة (العمليات، الوقت) على المحور الصادي. كل فئة تعقيد تنتج منحنى مميزاً. يمكنك التعرف على معدل نمو الخوارزمية من شكل منحنى الأداء الخاص بها.
O(1) — خط أفقي مسطح. الدالة f(N) = 1. لا ميل. التكلفة لا تتغير أبداً بغض النظر عن N. البحث في جدول التجزئة: سواء كان الجدول يحتوي على 10 أو 10,000,000 عنصر، فإن حساب التجزئة الواحد ينقفز إلى الدلو الصحيح.
O(log N) — منحنى صعودي لطيف، الميل يتناقص. عند N = 1,000,000: التكلفة ≈ 20 عملية. يرتفع المنحنى بشكل حاد عند N الصغير، ثم يتسطح. كل مضاعفة لـ N تضيف وحدة واحدة بالضبط من التكلفة.
O(N) — خط قطري مستقيم. الميل = 1 (بالمعنى التقاربي). التكلفة تنمو بنفس معدل N. إذا ثلث N، فإن التكلفة تثلث.
O(N log N) — قطر أكثر انحداراً مع انحناء صعودي طفيف. يقع فوق O(N) لكن أسفل O(N²). عامل السجل يضيف مضروباً سريع النمو ببطء للميل الخطي.
O(N²) — قطع مكافئ ينفتح للأعلى. الميل يزيد مع نمو N. عند N = 10: التكلفة = 100. عند N = 100: التكلفة = 10,000. عند N = 1,000: التكلفة = 1,000,000.
الفجوة المتنامية
النسبة O(N²) / O(N) = N. الفجوة بين القطع المكافئ والقطر تتسع مع نمو N. عند N = 10: فجوة 10×. عند N = 100: فجوة 100×. عند N = 1,000: فجوة 1,000×. عند N = 50,000: فجوة 50,000×. الفجوة تساوي دائماً N.
حساب فجوة المقياس
يحتوي رسم بياني كبير للاعتمادية على 50,000 حزمة (N = 50,000). خوارزمية واحدة تعمل في وقت O(N). الثانية تعمل في O(N²). عند هذا N، النسبة O(N²)/O(N) = N = 50,000.
تقسيم نقطة قطعة مستقيمة
البحث الثنائي كتقسيم متكرر
مصفوفة مرتبة من N عناصر تشكل قطعة مستقيمة بطول N. البحث الثنائي يقسم هذه القطعة بشكل متكرر:
1. أشر إلى نقطة منتصف القطعة المتبقية.
2. إذا كان الهدف < نقطة المنتصف: يختفي النصف الأيمن. كرر على النصف الأيسر.
3. إذا كان الهدف > نقطة المنتصف: يختفي النصف الأيسر. كرر على النصف الأيمن.
4. إذا كان الهدف = نقطة المنتصف: تم.
بعد k تقسيم، تصبح القطعة المتبقية طولها N / 2^k. ينتهي البحث عندما يساوي هذا الطول 1:
N / 2^k = 1 → 2^k = N → k = log₂N
لذا البحث الثنائي على N عنصر يتطلب على الأكثر log₂N مقارنة.
التنصيف و المضاعفة: وجهان لنفس المنحنى
التنصيف و المضاعفة معكوسات هندسية. منحنى الأسس 2^k ومنحنى اللوغاريتم log₂N هما انعكاسات لبعضهما عبر الخط y = x.
فكر في طي الورق: تبدأ الورقة بسماكة 0.1 ملم. كل طية تضاعف السماكة. بعد 42 طية: 0.1 ملم × 2^42 ≈ 439,804 كم — بعد القمر (384,400 كم). البحث الثنائي يشغل المعكوس: ابدأ بـ N عنصر، كل خطوة تنصف العدد، صل إلى عنصر واحد في log₂N خطوات.
الهندسة: التقسيم هو عملية متشابهة ذاتياً. كل تقسيم ينتج نصفين يبدآن متطابقين في الهيكل للكل. التكرار و اللوغاريتمات تشاركان هذا التشابه الذاتي.
المقارنات و المضاعفات
مصفوفة مرتبة تحتوي على 1,048,576 عنصراً. ملاحظة: 1,048,576 = 2^20.
دالة التجزئة كخريطة هندسية
دالة التجزئة كدالة
يربط جدول التجزئة مفتاحاً بدلو باستخدام دالة تجزئة:
bucket = hash(key) mod table_size
هذه دالة بالمعنى الرياضي الصارم: تربط مجالاً (جميع المفاتيح الممكنة) بمدى (مؤشرات الدلو من 0 إلى table_size − 1). الصورة الهندسية: المفاتيح تحتل مساحة واحدة؛ الدلاء تحتل أخرى. دالة التجزئة تعكس المفاتيح على مؤشرات الدلو.
البحث O(1) — قفزة مباشرة، بدون بحث. تحسب دالة التجزئة مؤشر الدلو في وقت ثابت. قفز مباشرة إلى هذا الدلو. لا عبور، لا حلقة مقارنة.
عامل التحميل. عند عامل تحميل 0.75، 75% من الدلاء تحتوي على عنصر واحد على الأقل. فوق ~0.9، التصادمات تزيد: مفتاحان يتجزآن إلى نفس الدلو، مكونين سلسلة من العناصر داخل هذا الدلو. البحث في سلسلة طويلة ينخفض إلى O(N) في أسوأ الحالات.
جودة التوزيع كهندسة
دالة تجزئة موزعة جيداً تنشر المفاتيح بشكل موحد عبر جميع الدلاء. هندسياً: نطاق الدالة يغطي codomain الخاص بها بالتساوي. كل دلو يتلقى تقريباً N / table_size مفاتيح.
دالة تجزئة رديئة تجمع المفاتيح في عدد قليل من الدلاء. هندسياً: نطاق الدالة ينهار إلى مجموعة فرعية من codomain — معظم المفاتيح تعكس إلى نفس النقاط القليلة. الدلاء المتبقية تجلس فارغة.
الاتصال بـ MOAD-0001
استبدال قائمة بمجموعة يصلح MOAD-0001 لأن مجموعة تستخدم جدول تجزئة داخلياً. مسح قائمة O(N) → بحث جدول تجزئة O(1). هندسياً: العبور الخطي على طول تسلسل يتحول إلى إسقاط مباشر عبر دالة. التسلسل يختفي؛ الدالة تحله محل.
تحليل تجزئة موزعة بشكل سيء
يحتوي جدول تجزئة على 1,000 دلو و 900 عنصر (عامل تحميل 0.9). دالة تجزئة سيئة ترسل 500 من تلك العناصر إلى نفس الدلو.