إذا قمت بالتجول في القائمة وحذفت كل عنصر غير مرتب صادفته، فكم عدد العناصر المتبقية في المتوسط؟

Question

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

مثال:سيتم حذف العناصر المميزة بنجمة في هذه القائمة أثناء التنقل.

[1, 4, 2*, 3*, 5, 7, 6*] -> [1, 4, 5, 7]

سؤالي هو:في المتوسط، كم سيكون طول القائمة المتبقية؟وهل هناك شكل بسيط/واضح لتوزيع هذا؟

وكمتابعة واحدة:إذا استخدمنا هذا لخوارزمية فرز (تسمى Drop Sort)، فماذا سيكون وقت التشغيل؟لكي نكون واضحين، ستكون الخوارزمية شيئًا مثل هذا:$$ extit{DropSort}( ext{list}) = extit{دمج}( ext{القائمة المتبقية}، extit{DropSort}( ext{القائمة المرفوضة}))$$

هذا السؤال مستوحى من هذا ص / مبرمجالفكاهة آخر.

Answer 1

يمكنك حساب المتوسط ​​باستخدام خطية التوقع.

دع المتغير العشوائي $X$ تشير إلى عدد العناصر التي تم الاحتفاظ بها.يترك $X_i$ يكون مؤشرا r.v.هذا هو 1 إذا $i$يتم الاحتفاظ بالعنصر، أو 0 خلاف ذلك.ثم $X = X_1+\النقاط + X_n$, ، لذا

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1] .$$

الآن $i$يتم الاحتفاظ بالعنصر إذا وفقط إذا كان العدد الأكبر بين العناصر الأولى $i$ العناصر في القائمة.لذلك، $\Pr[X_i=1]=\frac{1}{i}$, ، لذا

$$\mathbb{E[X] = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \approx \log(n) + \gamma $$

وبعبارة أخرى، فإن متوسط ​​طول القائمة المتبقية هو $O(\log n)$.

لا أعرف ما هو التوزيع.

كدليل إرشادي، فإن وقت التشغيل المتوقع لـ Drop Sort سوف يفي بتكرار شيء من هذا القبيل $T(n) \approx T(n-\log(n)) + O(n)$, ، والذي يتوافق مع $O\left(\frac{n^2}{\log n} ight)$ وقت.