احتمال أن اثنين من العناصر مقارنة في العشوائية فرز سريع

Question

لدي مشكلة في جزء محدد من العشوائية سريعة نوع التحليل.

حسب العشوائية سريعة-خوارزمية الفرز محور يتم اختياره من معين فرعية على الذي يدعى من عشوائية مؤشر بدلا من مجرد اختيار مؤشر محدد في كل مرة.

لنفترض الآن أن نقدم مجموعة من حجم أقول $n$ لدينا العشوائية فرز سريع الخوارزمية.

الآن أرجو إلقاء نظرة على دليل يما-7.1 في النص أدناه.الآن نحن قدمنا مجموعة لدينا خوارزمية والتي يمكن أن يكون من أي التقليب من العناصر ، ولكن في الفقرة بعد إثبات $يما-7.1$.

لماذا هو مؤلف النظر في فرز سبيل المثال لدينا مجموعة الإدخال أثناء القيام التحليل ؟

وعلاوة على ذلك إذا نظرة على النص بعد المعادلة $(7.2)$ حيث هناك ما يبرره منطق إيجاد احتمال أن $z_i$ يجوز مقارنة مع $z_j$ في الخوارزمية.الآن في أن يتم النظر في فرعية {$z_i$,...,$z_j$}.أليست هذه حالة من المقارنة $z_i$,$z_j$ الحصول محددة جدا إذا اعتبرنا أن فرعية فقط ؟ أنا أقصد أن أقول نحن العشوائية باستخدام نهج احتمال المقارنة قد تكون مشتقة باستخدام أكثر أوسع تبدو مثل التقليب من جميع الحالات المحتملة أو نحو ذلك.

أننا باستخدام مجموعة فرعية و هذا أيضا فرز غير مقنع كيف يمكننا الحصول على صحة احتمال لدينا خوارزمية...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

واحتمال $1/(j-i+1)$ -> total no.من العناصر في فرعية هي أيضا ثابتة محددة $i$ و $j$

في النظر في احتمال مقارنة $z_i$,$z_j$, المجموعة الفرعية التي عنصرين هناك و الذي سيتم تقسيم يمكن أن يكون أي شيء(أنا.هـ تتألف من أي عنصر) و من أي حجم (وليس فقط $j-i+1$)...

قد يكون العشوائية الشرط هو في الواقع أخذ كل شيء في الحساب ولكن أنا لا تحصل على ذلك.يرجى يمكن لك أن تشرح لي منطق أنها تستخدم لإيجاد قال احتمال يرجى أيضا تقنعني بأننا بشكل صحيح إيجاد احتمال المقارنة.

للإشارة أنا ربط المقابلة صفحات من مقدمة إلى الخوارزميات 3RD ED-- CLRS

Answer 1

بسيط جدا برهان:أزعم أنه إذا كان هناك د الصحيحه مع القيم بين x و y و هناك n ≥ 2 العناصر في الصفيف ، ثم احتمال أن x و y هي مقارنة 2 / (d + 2) ، مستقلة n.

الدليل التعريفي:إذا كان n = 2 ثم بوضوح d = 0, حتى المطالبة هو أن x و y هي مقارنة مع احتمال 2 / (0 + 2) = 1.وهذا أيضا واضح الصحيح ، حيث x و y يجب أن تكون مقارنة.

الآن دعونا n ≥ 3.لأول التقسيم ، نختار المحور عشوائيا.كل عنصر صفيف مقارنة المحور ، أي مقارنات أخرى مصنوعة.حتى إذا كان عن طريق الصدفة نختار x أو y باعتبارها محور x و y سوف تكون مقارنة.احتمال 2 / ن.إذا كان عن طريق الصدفة نختار واحدة من د العناصر مع القيم بين x و y ، ثم التقسيم سوف تتحرك x إلى قسم واحد و y إلى أخرى ، لذلك فهي لا مقارنة.إذا كان علينا أن نختار واحدة من n - d - 2 العناصر ، ثم x و y في نهاية المطاف في نفس القسم و التعريف بها أنها ستكون مقارنة مع احتمال 2 / (d + 2).

وبالتالي فإن احتمال أن x و y هي مقارنة

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

هذا بالطبع على نفس النتيجة كما يوفال ، منذ |j - i| = d + 1.على randomising يجعل التحليل السهل جدا - لو قلنا على سبيل المثال "إذا كان n > 5 ثم نختار 5 عناصر عشوائيا اختيار الوسيط من تلك 5 المحور" ، التحليل سيكون أكثر تعقيدا من ذلك بكثير.

PS.البرهان في الورقة هو أسهل بكثير:كما يمكنك تقسيم مجموعة ، $x_i$ و $x_j$ تبقى في نفس الفرعية قسم حتى محور مع <= المحورية <= j يستخدم.إذا كان هذا المحور هو i أو j ثم $x_i$ و $x_j$ مقارنة وإلا فهي ليست مقارنة.وبالتالي فإن فرصة 2 / (abs (j-i) + 1).

Answer 2

فكرة الإثبات هو حساب، لأي عنصرين $ X، $ $ في الصفيف، الاحتمال الذي تتم مقارنتها في الخوارزمية. يمكن أن يعتمد هذا الاحتمال على الصفيف بأكمله. ومع ذلك، اتضح أنه يمكنك حسابها فقط بالنظر إلى إحصاءات الطلبات فقط من $ x، y $ ، أي ترتيبها النسبي في الصفيف الفرز. إذا كنت تعرف أن $ x $ هو $ i $ $ أصغر عنصر في الصفيف وهذا $ y $ هو $ J $ أصغر عنصر في الصفيف، ثم احتمال أن $ x، $ $ تتم مقارنة $ \ frac {ji | +1} $ .

هذه ليست حالة خاصة - كل عنصر $ x $ في الصفيف هو $ i $ $ أصغر عنصر، بالنسبة لبعض قيمة $ I i $ . هذه مجرد المعلومات ذات الصلة التي تسمح لنا بحساب الاحتمالية التي $ x $ و $ Y $