(۱۴ بهمن ۱۳۹۲ ۰۷:۴۵ ب.ظ)fulgent نوشته شده توسط:  سلام
دوتا سوال دارم ممنون میشم جواب بدین: (یه تردیدی تو جوابشون برام به وجود اومده!)

۱- یافتن عنصر میانه در یک آرایه مرتب شده از مرتبه O(1) است یا O(n) ؟

۲- مرتبه زمانی "یافتن کوچکترین عنصر در یک لیست که هر بار لیست را به قسمت مساوی تقسیم می کنیم " چیست؟

۱/ اولی که تابلو ۱ میشه . وقتی آرایه مرتبه که همه چی تمومه. میانه و ماکس و مین همه ۱ میشه
۲/ اگه منظورت لیست یپوندی هست که زمانش n میشه و اصلا لیست را نمیشه تقسیم کرد (مگر لیست های خاص)
و اگر منظورت از لیست همون آرایه است که اصلا این الگوریتم جواب نمیده. یا اگه جواب بده همون n میشه و جستجو خطی محسوب میشه
خلاصه اینکه تا این لیست چی باشه .

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

(14 بهمن ۱۳۹۲ ۰۷:۴۵ ب.ظ)fulgent نوشته شده توسط:  سلام
دوتا سوال دارم ممنون میشم جواب بدین: (یه تردیدی تو جوابشون برام به وجود اومده!)

۱- یافتن عنصر میانه در یک آرایه مرتب شده از مرتبه O(1) است یا O(n) ؟

۲- مرتبه زمانی "یافتن کوچکترین عنصر در یک لیست که هر بار لیست را به قسمت مساوی تقسیم می کنیم " چیست؟

۱/ اولی که تابلو ۱ میشه . وقتی آرایه مرتبه که همه چی تمومه. میانه و ماکس و مین همه ۱ میشه
۲/ اگه منظورت لیست یپوندی هست که زمانش n میشه و اصلا لیست را نمیشه تقسیم کرد (مگر لیست های خاص)
و اگر منظورت از لیست همون آرایه است که اصلا این الگوریتم جواب نمیده. یا اگه جواب بده همون n میشه و جستجو خطی محسوب میشه
خلاصه اینکه تا این لیست چی باشه .

ببخشید اقا مسعود عنصر میانه رو چطوری پیدا می کنن؟
می شه الگوریتم یا روشش رو بگید


برای سوال دوم هم مگه همون تقسیم و غلبه نمی شه هر بار لیست رو تقسیم کنیم به دو قسمت مساوی و کوچکترین اون قسمت رو پیدا کنیم؟

(۱۴ بهمن ۱۳۹۲ ۰۸:۳۸ ب.ظ)mehdi.m2 نوشته شده توسط:  ببخشید اقا مسعود عنصر میانه رو چطوری پیدا می کنن؟
می شه الگوریتم یا روشش رو بگید

$cout<<A[\frac{n}{2}]$
تموم
آرایه مرتب شده است

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

(14 بهمن ۱۳۹۲ ۰۷:۴۵ ب.ظ)fulgent نوشته شده توسط:  سلام
دوتا سوال دارم ممنون میشم جواب بدین: (یه تردیدی تو جوابشون برام به وجود اومده!)

۱- یافتن عنصر میانه در یک آرایه مرتب شده از مرتبه O(1) است یا O(n) ؟

۲- مرتبه زمانی "یافتن کوچکترین عنصر در یک لیست که هر بار لیست را به قسمت مساوی تقسیم می کنیم " چیست؟

۱/ اولی که تابلو ۱ میشه . وقتی آرایه مرتبه که همه چی تمومه. میانه و ماکس و مین همه ۱ میشه
۲/ اگه منظورت لیست یپوندی هست که زمانش n میشه و اصلا لیست را نمیشه تقسیم کرد (مگر لیست های خاص)
و اگر منظورت از لیست همون آرایه است که اصلا این الگوریتم جواب نمیده. یا اگه جواب بده همون n میشه و جستجو خطی محسوب میشه
خلاصه اینکه تا این لیست چی باشه .

۱- افرین منم میگم میشه از مرتبه ۱ ولی مدرسان تو جواب یکی از سوالاش نوشته از مرتبه n هست!!!
۲- منظور همون ارایه بود....پس همینم میشه از مرتبه n ، اره؟

برای سوال اوم هم میشه $O(1)$
$O(n)$ ولی $O(1)$ دقیق تره.

واسه سول دوم رابطه بازگشتیش فکر کنم بشه
T(n) = 2T(n/2) + n/2 - 1
که میشه nlgn

(۱۵ بهمن ۱۳۹۲ ۱۰:۴۴ ق.ظ)Riemann نوشته شده توسط:  برای سوال اوم هم میشه $O(1)$
$O(n)$ ولی $O(1)$ دقیق تره.

واسه سول دوم رابطه بازگشتیش فکر کنم بشه
T(n) = 2T(n/2) + n/2 - 1
که میشه nlgn

اشتباه می کنی هادی میشه
T(n) = 2T(n/2) +1

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

(15 بهمن ۱۳۹۲ ۱۰:۴۴ ق.ظ)Riemann نوشته شده توسط:  برای سوال اوم هم میشه $O(1)$
$O(n)$ ولی $O(1)$ دقیق تره.

واسه سول دوم رابطه بازگشتیش فکر کنم بشه
T(n) = 2T(n/2) + n/2 - 1
که میشه nlgn

اشتباه می کنی هادی میشه
T(n) = 2T(n/2) +1

بله درست میگی از پایین میاد بالا!

از دوستانی که وقت گذاشتن متشکرم

---

یه چیزی! الان جواب سوال دوم شد از مرتبه n، درسته؟
سوال پارسال ساختمان داده که می خواست عنصر مینیمم رو پیدا کنه چون گفته بود میانگین جواب میشد از مرتبه log n اره؟ یعنی فقط چون گفته بود میانگین، وگرنه همونم میشد از مرتبه n درسته؟

(۱۵ بهمن ۱۳۹۲ ۱۱:۱۳ ق.ظ)fulgent نوشته شده توسط:  از دوستانی که وقت گذاشتن متشکرم

---

یه چیزی! الان جواب سوال دوم شد از مرتبه n، درسته؟
سوال پارسال ساختمان داده که می خواست عنصر مینیمم رو پیدا کنه چون گفته بود میانگین جواب میشد از مرتبه log n اره؟ یعنی فقط چون گفته بود میانگین، وگرنه همونم میشد از مرتبه n درسته؟

اصلا اون سوال یه چیز دیگه بود
اون می گفت چند بار متغییر مینیمم عوض میشه تا به آخر لیست برسیم
این میگه پیچیدگی پیدا کردن مینیمم چی هست

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

(15 بهمن ۱۳۹۲ ۱۱:۱۳ ق.ظ)fulgent نوشته شده توسط:  از دوستانی که وقت گذاشتن متشکرم

---

یه چیزی! الان جواب سوال دوم شد از مرتبه n، درسته؟
سوال پارسال ساختمان داده که می خواست عنصر مینیمم رو پیدا کنه چون گفته بود میانگین جواب میشد از مرتبه log n اره؟ یعنی فقط چون گفته بود میانگین، وگرنه همونم میشد از مرتبه n درسته؟

اصلا اون سوال یه چیز دیگه بود
اون می گفت چند بار متغییر مینیمم عوض میشه تا به آخر لیست برسیم
این میگه پیچیدگی پیدا کردن مینیمم چی هست

بله حواسم نبود به صورت سوالش، خب حالا اگر گفته بود تعداد مقایسه چی؟ اون موقع میشه مرتبه n، اره؟

این میانه که میگین میانه کل لیست مرتب؟یا اینکه هی لیست تقسیم دو شه بعد هی میانشو بدست میارین؟ یعتی یه میانه فقط یا چندتا؟

(۱۴ بهمن ۱۳۹۳ ۰۱:۴۹ ق.ظ)ریحان نوشته شده توسط:  این میانه که میگین میانه کل لیست مرتب؟یا اینکه هی لیست تقسیم دو شه بعد هی میانشو بدست میارین؟ یعتی یه میانه فقط یا چندتا؟

میانه ی لیست مرتب..مثلا ۱۲۳۴۵میانه ک عدد۳هست با O)1(
میشه پیدا کرد.دوباره ک لیست سمت چپ یا راستو بخوای میانه شو پیدا کنی باز ازO)1
چون اون زیرارایه ها هم مرتب هستن.

بله درسته.ممنون