تالار گفتمان مانشت

اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
1-[tex]O(log n)[/tex]
2-[tex]O(n log n)[/tex]
3-[tex]O(n^{2})[/tex]
4-[tex]O(n)[/tex]

اگه اشتباه نکنم تمرین 7-2.3 کتاب CLRS هست

(06 بهمن 1392 01:15 ق.ظ)MEHDI_M نوشته شده توسط: [ -> ]اگه اشتباه نکنم تمرین ۷-۲/۳ کتاب CLRS هست

جواب رو یادتون هست بگین ؟

سلام اگه جواب میشه [tex]O(nlogn)[/tex] بگین من توضیحمو بدم (البته اگه این n عدد صخیخ در بازه 0 تا 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]

(05 بهمن 1392 06:19 ب.ظ)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 میشه

(18 بهمن 1392 08:46 ب.ظ)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. مگه نه؟

---

(18 بهمن 1392 08:48 ب.ظ)explorer نوشته شده توسط: [ -> ]

(05 بهمن 1392 06:19 ب.ظ)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 مرتب نمی کنند زمانش کمتر میشه...

(18 بهمن 1392 10:10 ب.ظ)fulgent نوشته شده توسط: [ -> ]زمان جستجوی دودویی میشه از مرتبه log n. مگه نه؟

سپاس درستش کردم ؛ مثل اینکه مغز محترم روزای آخری حسابی خسته ست

(18 بهمن 1392 08:46 ب.ظ)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 میشه

(19 بهمن 1392 02:23 ب.ظ)mohammad.ardeshiri نوشته شده توسط: [ -> ]

(18 بهمن 1392 08:46 ب.ظ)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]

(19 بهمن 1392 03:46 ب.ظ)hosshah نوشته شده توسط: [ -> ]ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره

خب پس زمان مرتب سازی رو چه جوری حساب کردین

(19 بهمن 1392 08:32 ب.ظ)zahra2012 نوشته شده توسط: [ -> ]خب پس زمان مرتب سازی رو چه جوری حساب کردین

من با اونی که الگوریتمو گفته فرق دارما
از همون مرتب سازی سریع یا ادغامی یا ...

(19 بهمن 1392 08:51 ب.ظ)hosshah نوشته شده توسط: [ -> ]

(19 بهمن 1392 08:32 ب.ظ)zahra2012 نوشته شده توسط: [ -> ]خب پس زمان مرتب سازی رو چه جوری حساب کردین

من با اونی که الگوریتمو گفته فرق دارما
از همون مرتب سازی سریع یا ادغامی یا ...