المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:الگوریتم ها:سوال ۲

سوال ۲

یک ماشین $k$-خفن ماشینی است که اگر $k$ عنصر متوالی از یک آرایه را به آن بدهیم آن را در $Ο(1)$ مرتب می‌کند.

  1. ثابت کنید به‌ازای $k=c>1$ (یعنی یک عدد ثابت) مرتب کردن یک آرایه با اندازه $n$ بوسیله یک ماشین $k$-خفن در بدترین حالت از $Ω(n^2)$ می‌باشد. دقت کنید در این قسمت و قسمت بعد ما به خود آرایه دسترسی نداریم و فقط می‌توانیم ماشین را کنترل کنیم.
  2. ثابت کنید که به ازای $k=n/c$ مرتب کردن یک آرایه به طول $n$ از $Ο(c^2)$ است.

ابزار صفحه