فرض کنید آرایهای به طول n داریم که به شکل حلقوی مرتب صعودی است. برای مثال آرایه زیر: ۴۰ ۵۰ ۶۰ ۷۰ ۸۰ ۹۰ ۱۰ ۲۰ ۳۰ ---- ---- ---- ---- ---- ---- ---- ---- ---- میخواهیم الگوریتمی بنویسیم که ⌊ √n ⌋ امین کوچکترین عنصر این آرایه را بیابیم، مرتبه زمانی این الگوریتم چیست؟

سوال ۶۲ کنکور ارشد مهندسی کامپیوتر ۱۴۰۳

اهمیت

۰/۵

فرض کنید آرایه‌ای به طول n داریم که به شکل حلقوی مرتب صعودی است. برای مثال آرایه زیر:

۴۰	۵۰	۶۰	۷۰	۸۰	۹۰	۱۰	۲۰	۳۰

می‌خواهیم الگوریتمی بنویسیم که $\lfloor \sqrt{n} \rfloor$ امین کوچک‌ترین عنصر این آرایه را بیابیم، مرتبه زمانی این الگوریتم چیست؟

#binary-search#rotated-sorted-array#order-statistics#time-complexity#logarithmic