صفحهها: ۱ ۲
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۸ ب.ظ)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)....
نظرتونو بگید مرسی....
(۱۹ بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)hosshah نوشته شده توسط: ما اینجا نمیتونیم از Count Sort استفاده کنیممگه radix هست که با اعداد n رقمی بشه n^2 ? اون radix هست که با عدد n رقمی میشه n^2
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد 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 بزرگترین عنصر باشه