ما هو التعقيد الزمني المتوقع للتحقق من المساواة بين سلسلتين عشوائيتين؟

Question

الإجابة البسيطة (الساذجة؟) ستكون O(n) حيث n هو طول السلسلة الأقصر.لأنه في أسوأ الحالات يجب عليك مقارنة كل زوج من الأحرف.

حتى الان جيدة جدا.أعتقد أننا يمكن أن نتفق جميعًا على التحقق من تساوي اثنين يساوي طول تتطلب السلاسل وقت تشغيل O(n).

ومع ذلك، فإن العديد من اللغات (معظمها؟) (أنا أستخدم Python 3.7) تخزن أطوال السلاسل للسماح بعمليات بحث ثابتة للوقت.لذلك في حالة اثنين طول غير متساو السلاسل، يمكنك ببساطة التحقق منها len(string_1) != len(string_2) في وقت ثابت.يمكنك التحقق من أن Python 3 يقوم بالفعل بهذا التحسين.

الآن، إذا كنا نتحقق من مساواة اثنين حقا سلاسل عشوائية (ذات طول تعسفي) فمن الأرجح (بشكل لا نهائي، على ما أعتقد) أن تكون السلاسل ذات طول غير متساوٍ من الطول المتساوي.وهو ما يضمن (إحصائيًا) إمكانية مقارنتها دائمًا تقريبًا في وقت ثابت.

لذلك يمكننا مقارنة سلسلتين عشوائيتين بمتوسط ​​O(1)، مع أسوأ حالة نادرة جدًا لـ O(n).هل يجب أن نعتبر مقارنات السلاسل O(1) بنفس الطريقة التي نعتبر بها عمليات البحث في جدول التجزئة O(1)؟

Answer 1

من أجل مناقشة التعقيد الزمني المتوقع لعملية ما، يجب عليك تحديد التوزيع على المدخلات، وكذلك شرح ما تعنيه بـ $ن$.

ومع ذلك، يجب على المرء أن يكون حذرا.على سبيل المثال، خذ بعين الاعتبار الاقتراح الموجود في التعليقات، للنظر في نوع من التوزيع على كلمات يبلغ طولها 20 على الأكثر.في هذه الحالة، مقارنة السلسلة بشكل واضح $O(1)$, لأن 20 هو مجرد ثابت.هناك عدة طرق لتجنب ذلك:

• اطلب تعقيدًا زمنيًا غير مقارب.نظرًا لأن تعقيد الوقت يعتمد بشكل كبير على نموذج الحساب، يمكنك حساب (على سبيل المثال) عدد خلايا ذاكرة الإدخال التي تم الوصول إليها.

• يمكنك تحديد توزيع الإدخال الذي يعتمد على المعلمة $م$, ، ثم اسأل عن التعقيد المقارب من حيث $م$.

هنا مثال.نظرا لسلسلتين ثنائيتين عشوائيتين من الطول $ن$, ، سيكون هناك ما يقرب من 4 عمليات وصول متوقعة.في المقابل، إذا تم اختيار السلاسل بشكل عشوائي من المجموعة $0^i1^{n-i}$, ، سيكون عدد مرات الوصول تقريبًا $(2/3)ن$.يمكن فصل هذين التوزيعين حتى لو استخدمنا التدوين المقارب:تعمل الخوارزمية $O(1)$ في التوزيعة الأولى وفي $\ثيتا(ن)$ في الثاني.

مسألة أخرى هي معنى $ن$.خذ بعين الاعتبار على سبيل المثال سلسلة $0^م$, ، أين $m \sim G(1/2)$ هو متغير عشوائي هندسي.عند التشغيل على مدخلات الأطوال $أ،ب$, ، وقت التشغيل هو $\ثيتا(\دقيقة(أ,ب))$.كيف ينبغي لنا أن نعبر عن هذا من حيث $ن = أ+ب$؟أحد الخيارات هو السؤال عن وقت التشغيل المتوقع نظرًا لطول الإدخال $ن$.في هذه الحالة،$$ \mathbb{E}[\min(a,b)] = \sum_{a=1}^{n-1} \frac{(1/2)^a (1/2)^{n-1-a}}{\sum_{a'=1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a'}} \min(a,n-a) = \frac{1}{n-1} \sum_{a=1}^{n-1} \min(a,n-a) \approx \frac{n}{4}, $$لذا فإن وقت التشغيل المتوقع هو $\ثيتا(ن)$.