صفحه‌ها: ۱ ۲
اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
اگه اشتباه نکنم تمرین ۷-۲/۳ کتاب CLRS هست
(۰۶ بهمن ۱۳۹۲ ۰۱:۱۵ ق.ظ)MEHDI_M نوشته شده توسط: اگه اشتباه نکنم تمرین ۷-۲/۳ کتاب CLRS هست
جواب رو یادتون هست بگین ؟
سلام اگه جواب میشه [tex]O(nlogn)[/tex] بگین من توضیحمو بدم (البته اگه این n عدد صخیخ در بازه ۰ تا n-1 باشن از مرتبه n میشه ولی چون چیزی تو صورت سوال نگفته همون nlogn میشه به نظرم)
اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
(۰۵ بهمن ۱۳۹۲ ۰۶:۱۹ ب.ظ)tabassomesayna نوشته شده توسط: اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
شما عمل پارتیشن رو حول x انجام بده O (n)
حالا سمت چپ x اعداد کوچکتر از x هستند
با nlogn مرتب میشن
حالا به ازای هر عنصر مثه y ، عنصر x-y رو توی قسمت چپ x سرچ میکنیم
کلا nlogn میشه
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)tayebe68 نوشته شده توسط: اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(n)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
زمان جستجوی دودویی میشه از مرتبه log n. مگه نه؟
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۸ ب.ظ)explorer نوشته شده توسط:(05 بهمن ۱۳۹۲ ۰۶:۱۹ ب.ظ)tabassomesayna نوشته شده توسط: اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
شما عمل پارتیشن رو حول x انجام بده O (n)
حالا سمت چپ x اعداد کوچکتر از x هستند
با nlogn مرتب میشن
حالا به ازای هر عنصر مثه y ، عنصر x-y رو توی قسمت چپ x سرچ میکنیم
کلا nlogn میشه
اعداد کوچکتر از x رو در زمان nlogn مرتب نمی کنند زمانش کمتر میشه...
(۱۸ بهمن ۱۳۹۲ ۱۰:۱۰ ب.ظ)fulgent نوشته شده توسط: زمان جستجوی دودویی میشه از مرتبه log n. مگه نه؟
سپاس درستش کردم ؛ مثل اینکه مغز محترم روزای آخری حسابی خسته ست
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)tayebe68 نوشته شده توسط: اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]جوابتون دقیقا درسته ولی یه اشتباه کوچیک داره گفتم شما توجه نکردین بد نیست بگم که تو جلسه اشتباه نکنین
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
عداد آرایه صیح هست با O(m+n)l آرایه مرتب میشه بعد مراحلی که tayebe68 گفتند
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
اجرا میشه و بعد از مرتبه o(n)l میشه
(۱۹ بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)mohammad.ardeshiri نوشته شده توسط:(18 بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)tayebe68 نوشته شده توسط: اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]جوابتون دقیقا درسته ولی یه اشتباه کوچیک داره گفتم شما توجه نکردین بد نیست بگم که تو جلسه اشتباه نکنین
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
عداد آرایه صیح هست با O(m+n)l آرایه مرتب میشه بعد مراحلی که tayebe68 گفتند
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
اجرا میشه و بعد از مرتبه o(n)l میشه
با استفاده از مرتب سازی شمارشی به o(m+n) l رسیدین پس جواب کلی o(n)l هست؟
ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره
به دلیل ابهامی که تو سؤال پیش اومده بود، من این عکس رو میزارم، راه حل هم که دوستان خوب توضیح دادن
شماره تمرین رو یکی از دوستان زحمت کشیده بود گذاشته بود، من فقط پیداش کردم
[attachment=15302]
(۱۹ بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)hosshah نوشته شده توسط: ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره
خب پس زمان مرتب سازی رو چه جوری حساب کردین
(۱۹ بهمن ۱۳۹۲ ۰۸:۳۲ ب.ظ)zahra2012 نوشته شده توسط: خب پس زمان مرتب سازی رو چه جوری حساب کردین
من با اونی که الگوریتمو گفته فرق دارما
از همون مرتب سازی سریع یا ادغامی یا ...
(۱۹ بهمن ۱۳۹۲ ۰۸:۵۱ ب.ظ)hosshah نوشته شده توسط:(19 بهمن ۱۳۹۲ ۰۸:۳۲ ب.ظ)zahra2012 نوشته شده توسط: خب پس زمان مرتب سازی رو چه جوری حساب کردین
من با اونی که الگوریتمو گفته فرق دارما
از همون مرتب سازی سریع یا ادغامی یا ...