آرایه نامتناهی A را در نظر بگیرید. فرض کنید در n خانه اول این آرایه n عدد صحیح متمایز بهصورت مرتب شده (صعودی) قرار گرفتهاند و بقیه خانههای آرایه با ∞ پر شده است. بازای عدد x داده شده میخواهیم بررسی کنیم آیا عدد x در آرایه وجود دارد یا خیر. با چه مرتبه زمانی میتوان به این پرسش پاسخ داد؟ (با فرض آن که مقدار n را از قبل نمیدانیم.)

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

طراحی الگوریتم‌هامتوسطمرتب‌سازی و پیچیدگی مبتنی بر مقایسه

اهمیت

۰/۵

آرایه نامتناهی A را در نظر بگیرید. فرض کنید در n خانه اول این آرایه n عدد صحیح متمایز به‌صورت مرتب شده (صعودی) قرار گرفته‌اند و بقیه خانه‌های آرایه با $\infty$ پر شده است. بازای عدد x داده شده می‌خواهیم بررسی کنیم آیا عدد x در آرایه وجود دارد یا خیر. با چه مرتبه زمانی می‌توان به این پرسش پاسخ داد؟ (با فرض آن که مقدار n را از قبل نمی‌دانیم.)

#exponential-search#galloping-search#binary-search#unbounded-array#sorted-array#logarithmic-time