المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

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

  1. ثابت کنید ‎$f(n) \in \Omega(\log n)$‎
  2. ثابت کنید ‎$f(n) \in O(\sqrt{n})$‎

ابزار صفحه