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

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

اهمیت

۰/۵

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

مسئله ۱-مجموعه در زمان $O(1)$ قابل حل است.
مسئله ۲-مجموعه در زمان $O(n)$ قابل حل است.
مسئله ۳-مجموعه در زمان $O(n^{۲})$ قابل حل است.

#3-sum#k-sum#subset-sum#time-complexity#sorting#lower-bound