علوم کامپیوتر ۸۸ :
اگر n عدد صحیح داشته باشیم که یکی از انها x باشد الگوریتمی که تشخیص دهد دو عدد در این اعداد موجوده که مجموعشون x میشه دارای کدام پیچیدگی است؟
دوستان جواب شده n لوگ n .در ابتدا لیستو مرتب کرده با مرتبه n لوگn بعد هم در یک حلفه از ۱ تا n از طریق جستجو دودویی گشته تا
x - a[i را پیدا کنه...اینم میشه n لوگ n در نهایتم شده همین n لوگ n
میخوام ببینم چرا لیستو مرتب کرده؟ ایا نمیشد نامرتب مقدار x-a[i را توی یه حلقه پیدا میکردیم؟
بعد اگه سوال اینطور بود که X را نداده بود و میگفت کلا ببینین توی لیست دو عددی هستن که مجموعشون عددی دیگه در لیست بشه چی میشد؟
ممنون
(۰۱ دى ۱۳۹۳ ۱۲:۲۶ ب.ظ)ریحان نوشته شده توسط: علوم کامپیوتر ۸۸ :
اگر n عدد صحیح داشته باشیم که یکی از انها x باشد الگوریتمی که تشخیص دهد دو عدد در این اعداد موجوده که مجموعشون x میشه دارای کدام پیچیدگی است؟
دوستان جواب شده n لوگ n .در ابتدا لیستو مرتب کرده با مرتبه n لوگn بعد هم در یک حلفه از ۱ تا n از طریق جستجو دودویی گشته تا
x - a[i را پیدا کنه...اینم میشه n لوگ n در نهایتم شده همین n لوگ n
میخوام ببینم چرا لیستو مرتب کرده؟ ایا نمیشد نامرتب مقدار x-a[i را توی یه حلقه پیدا میکردیم؟
بعد اگه سوال اینطور بود که X را نداده بود و میگفت کلا ببینین توی لیست دو عددی هستن که مجموعشون عددی دیگه در لیست بشه چی میشد؟
ممنون
سلام
آره میشده با ارایه نا مرتب اجرا کنه ولی مرتبه زمانی اون فکر کنم باید از O(n^2)s میشد(یک حلقه برای یک عنصر که با n عنصر مقایشه بشه یک حلقه برای n عنصر) که اگه با آرایه مرتب بریم خیلی از مقایسه ها کمتر انجام میشد
در مورد سوال بعدی فکر کنم باید از o(n^2)s بشه چون یک مرتب سازی داری از nlogn بعد باید هر عنصر رو با تمام عناصر بعد خودش جمع بشه که میشه از n^2 بعد باید جستجو بشه که از logn هستش (هر چند احتمال میدم از O(n^2*logn)s هم باشه)
ممنون منم خودم حدس میزنم سوال اولم اگه نا مرتب باشه لیست بشه N به توان ۲
اما سوال بدی رو نفهمیدم...
دوستان نظر میدین شما هم....