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

دنباله A[1..n] یک دنباله دوآهنگی (Bitonic) است، بدین معنی که هرگاه عناصر دنباله را به‌ترتیب دور یک دایره بنشانیم، یک عنصر یافت می‌شود که دنباله عناصر بعدی ابتدا صعودی و سپس نزولی هستند. بهترین زمان…

در الگوریتم مرتب‌سازی Insertion Sort، اگر برای جستجوی مکان مناسب عنصر جاری به جای جستجوی خطی از جستجوی دودویی استفاده کنیم، کدام مورد زیر درخصوص پیچیدگی زمانی آن در بدترین حالت درست است؟

آرایه A به طول n را K- مرتب می‌کنیم. هرگاه برای هر i که k ≤ i ≤ n-k داشته باشیم A[i-k] ≤ A[i] ≤ A[i+k] ، یعنی آرایه A به k لیست مرتب که هر کدام تقریباً n/k عنصر دارند افراز می‌شود. فرض کنید A یک…

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

یک آرایه دوبعدی n × n از اعداد داده شده‌است که هر سطر به‌صورت صعودی از چپ به راست و هر ستون به‌صورت صعودی از بالا به پایین مرتب شده‌است. کمترین پیچیدگی زمانی برای پیداکردن یک عدد داده‌شده در این…

فرض کنید A = [a_1, a_2, …, a_n] آرایه‌ای از اعداد صحیح متمایز باشد و k یک عدد صحیح داده شده باشد. هدف این است که دو عدد متمایز از A را پیدا کنید که مجموع آنها دقیقاً k باشد، یا گزارش دهید که چنین…

آرایه A شامل n عدد داده شده است. هدف پیدا کردن تعداد جفت اندیس‌های i و j است، به‌گونه‌ای که A[i]× A[j] > i× j . این کار در چه زمانی قابل انجام است؟ (بهترین گزینه را انتخاب کنید.)

مسئله k-مجموعه بدین شکل تعریف می‌شود: مجموعه A از n عدد حقیقی و عدد k داده شده است. آیا k عضو از مجموعه A وجود دارند که جمع آنها صفر شود؟ چه تعداد از گزاره‌های زیر درست است؟ مسئله ۱-مجموعه در زمان…

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

یک ماتریس ۶۴ در ۶۴ داریم که درایه‌های آن همه ۰ یا ۱ هستند. می‌خواهیم این ماتریس را به‌صورت مارپیچی مرتب کنیم، یعنی اگر در انتها، سطر اول از راست به چپ به سطر دوم از راست به چپ و … بچسبانیم یک آرایهٔ…

می‌خواهیم k لیست مرتب، هرکدام با n/k عنصر را در هم ادغام کنیم و لیست مرتب n تایی ایجاد کنیم. برای این کار ابتدا لیست ۱ را با لیست ۲ ادغام می‌کنیم. سپس لیست حاصل را با لیست ۳ و به همین روند ادامه…

آرایه A به طول n به‌صورت حلقوی مرتب است. یعنی اگر ابتدا و انتهای A را به هم بچسبانیم از یک درایه به بعد آرایه مرتب است. برای مثال آرایه [۶۰, ۷۰, ۸۰, ۱۰, ۲۰, ۳۰, ۴۰, ۵۰] به‌صورت حلقوی مرتب است. بهترین…