سوال ۸۵ کنکور ارشد علوم کامپیوتر ۱۳۹۸

طراحی الگوریتمسختپیچیدگی مجانبی و نرخ رشد

اهمیت

۰/۵

فرض کنید می‌خواهیم n داده را با عوض کردن داده‌ها مرتب کنیم. در الگوریتم این محدودیت را اعمال می‌کنیم که عناصر A[i] با A[j] نمی‌تواند با هم عوض بشود مگر اینکه n√ > |i − j| باشد. بهترین حد پایین زمانی برای این الگوریتم کدام است؟

#lower-bound#inversions#sorting#adjacent-swap#bounded-distance-swap#potential-argument