اول آرایه رو مرتب می کنیم در زمان [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]

(۱۸ بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)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
پس همون مرتب سازی مبتنی بر مقایسه بهتره

(۱۹ بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)hosshah نوشته شده توسط:  ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره

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

(۱۹ بهمن ۱۳۹۲ ۰۸:۳۲ ب.ظ)zahra2012 نوشته شده توسط:  خب پس زمان مرتب سازی رو چه جوری حساب کردین

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

(۱۹ بهمن ۱۳۹۲ ۰۸:۵۱ ب.ظ)hosshah نوشته شده توسط:  

(19 بهمن ۱۳۹۲ ۰۸:۳۲ ب.ظ)zahra2012 نوشته شده توسط:  خب پس زمان مرتب سازی رو چه جوری حساب کردین

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

(۱۹ بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)hosshah نوشته شده توسط:  ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره

مگه radix هست که با اعداد n رقمی بشه n^2 ? اون radix هست که با عدد n رقمی میشه n^2


ولی حرفت در کل درسته ولی من الان بیشتر فکر کردم یعنی یه نیم ساعتی فکر کردم دیدم اصن جوال
(n/2)^ دو
میشه
شما حتی اگه با n هم مرتب کنی ونصفشو تو حالت متوسط بندازی بیرون
بازم n/2 میمونه که باید دو تا حلقه for بزاری به ازای هر i تمام j هارو برسی کنی که میشه n^2

(۲۱ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  مگه radix هست که با اعداد n رقمی بشه n^2 ? اون radix هست که با عدد n رقمی میشه n^2


ولی حرفت در کل درسته ولی من الان بیشتر فکر کردم یعنی یه نیم ساعتی فکر کردم دیدم اصن جوال
(n/2)^ دو
میشه
شما حتی اگه با n هم مرتب کنی ونصفشو تو حالت متوسط بندازی بیرون
بازم n/2 میمونه که باید دو تا حلقه for بزاری به ازای هر i تمام j هارو برسی کنی که میشه n^2

خب نه من منظورم از Count به تعداد n رقم تا بود دیگه که میشه همون radix میشه از مرتبه n^2
ولی کل الگوریتم از مرتبه همون nlogn ها!!!
اون حلقه ای که میخواد عددا رو پیدا کنه یه حلقه ست نه دو حلقه

(۲۱ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  شما حتی اگه با n هم مرتب کنی ونصفشو تو حالت متوسط بندازی بیرون
بازم n/2 میمونه که باید دو تا حلقه for بزاری به ازای هر i تمام j هارو برسی کنی که میشه n^2

چون برای اعداد بازه یا شرط خاصی معین نشده ، باید مرتب سازی مبتنی بر مقایسه داشته باشیم که بهترین زمانش میشه [tex]O(nlogn)[/tex]

اینجا چون که آرایه مرتبه نیازی نیست دو تا حلقه for بگیریم
این آرایه مرتب رو در نظر بگیرید [tex]\[2,4,5,7,9,11,13,15\][/tex] می خوایم دو عدد پیدا کنیم که مجموعشون بشه ۱۶: (فرض که j به ۱۵ اشاره می کنه، i به ۲):
اول ۲ و ۱۵ رو مقایسه می کنیم میشه ۱۷ که از ۱۶ بیشتره پس --j
حالا ۱۵=۲+۱۳ <16 پس ++i
بعدی ۱۷=۱۳+۴ >16 پس --j
بعدی ۱۵=۱۱+۴ <16 پس ++i
و در آخر ۱۶=۱۱+۵ که اینجا جواب رو پیدا کردیم، و زمان این جستجو [tex]O(n)[/tex] میشه حتی در بدترین حالت که x بزرگترین عنصر باشه

اگه اشتباه نکنم تمرین ۷-۲/۳ کتاب CLRS هست

(۰۶ بهمن ۱۳۹۲ ۰۱:۱۵ ق.ظ)MEHDI_M نوشته شده توسط:  اگه اشتباه نکنم تمرین ۷-۲/۳ کتاب CLRS هست

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

سلام اگه جواب میشه [tex]O(nlogn)[/tex] بگین من توضیحمو بدم (البته اگه این n عدد صخیخ در بازه ۰ تا n-1 باشن از مرتبه n میشه ولی چون چیزی تو صورت سوال نگفته همون nlogn میشه به نظرم)

(۰۵ بهمن ۱۳۹۲ ۰۶:۱۹ ب.ظ)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 میشه

(۱۸ بهمن ۱۳۹۲ ۰۸:۴۸ ب.ظ)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 ادامه بدیم؟به این صورت که دوباره پارتیشن بزنی و با میانه مقایشه کنیم اگر بازم میانه کوچکتر از x-y بود ادامه میدیم تا به عدد x-y برسیم اینطوری زمانش میشه o(n)....
نظرتونو بگید مرسی....

به دلیل ابهامی که تو سؤال پیش اومده بود، من این عکس رو میزارم، راه حل هم که دوستان خوب توضیح دادن
شماره تمرین رو یکی از دوستان زحمت کشیده بود گذاشته بود، من فقط پیداش کردم