Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:تئوری مقدماتی اول:سوال ۳

سوال ۳

یک جایگشت دلخواه از اعداد ‎1,2,,n‎ را می‌خواهیم با عمل «وارون‌ساز» مرتب کنیم. عمل وارون‌ساز به عملی می‌گوییم که در طی آن یک زیر دنباله از جایگشت انتخاب می‌کنیم و اعضای آن را وارون می‌کنیم. فرض کنید ‎f(n)‎ کمترین تعداد عمل وارون‌ساز لازم برای یک جایگشت دلخواه از ‎1,2,,n‎ باشد. مثلا برای جایگشت ‎3,5,1,4,2‎ این عدد برابر ‎2 است. زیرا کافیست در گام اول زیر دنباله‌ی ‎3,1‎ را انتخاب کنیم و به جایگشت ‎1,5,3,4,2‎ برسیم و در گام دوم زیردنباله‌ی ‎5,4,2‎ را انتخاب کنیم و به جایگشت مرتب شده برسیم.

  1. ثابت کنید ‎f(n)Ω(logn)
  2. ثابت کنید ‎f(n)O(n)

ابزار صفحه