Processing math: 20%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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

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

ابزار صفحه