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

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

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

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


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

(21 بهمن 1392 02:40 ب.ظ)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 ها!!!
اون حلقه ای که میخواد عددا رو پیدا کنه یه حلقه ست نه دو حلقه

(21 بهمن 1392 02:40 ب.ظ)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] می خوایم دو عدد پیدا کنیم که مجموعشون بشه 16: (فرض که j به 15 اشاره می کنه، i به 2):
اول 2 و 15 رو مقایسه می کنیم میشه 17 که از 16 بیشتره پس --j
حالا 15=2+13 <16 پس ++i
بعدی 17=13+4 >16 پس --j
بعدی 15=11+4 <16 پس ++i
و در آخر 16=11+5 که اینجا جواب رو پیدا کردیم، و زمان این جستجو [tex]O(n)[/tex] میشه حتی در بدترین حالت که x بزرگترین عنصر باشه