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