(۰۸ بهمن ۱۳۹۳ ۱۱:۰۵ ق.ظ)shamim_70 نوشته شده توسط: ادغام kارایه مرتب با n عنصر با روشی شما گفتید میشه nk...ولی اگ با درخت انتخابی حلش کنیم میشه حداگثر n log k!!که بهتر از روش اوله!
ولی متوجه نمیشم چجوری درخت رو میسازید اونم با n!!!!!!
براساس جستجو دودویی هم پیش برید برای nتا عنصردر حالت متوسط log nمقایسه لازم هست !!
فک کنم منظورتون اینه هردفعه با o(1) عنصر میانه رو پیدامی کنید میزارید ریشه واینکارو چون n بار انجام میدین میشه o(n)..!!درسته؟؟
بلی بله
ارتفاع درخت logn هست اما ما کاری به ارتفاع نداریم !! چون کافیه این کارو روی ارایه کنید! توجه کنید ک مقایسه ای در کار نیست فقط تقسیم و یافتن ریشه س چون ارایه مرتب بیده
در هر بار تویه o(1 ریشه رو پیدا میکنم یعنی ب ازای عناصر غیر برگ باید ریشه مشخص کنید ک از n هم کمتر است ولی همین حدوداست
هزینه کلی هم ک نوشتم براتون
اوکی من درمورد o(nبودنش توجیه شد!
ولی درباره اون فرمول نه!ک گفتین:
"به روش درخت انتخابی ک میشه
K log k+n log k
مجموع این هزینه میشه o(n log k"
n log kماله ادغام k ارایه مرتب هست!!(ک یبار دیگ هم گفتم مربوط به درخت انتخابی هست))..اون یکی چیه؟
(۰۸ بهمن ۱۳۹۳ ۰۱:۴۵ ب.ظ)shamim_70 نوشته شده توسط: اوکی من درمورد o(nبودنش توجیه شد!
ولی درباره اون فرمول نه!ک گفتین:
"به روش درخت انتخابی ک میشه
K log k+n log k
مجموع این هزینه میشه o(n log k"
n log kماله ادغام k ارایه مرتب هست!!(ک یبار دیگ هم گفتم مربوط به درخت انتخابی هست))..اون یکی چیه؟
Klogk ساخت مین هیپ اولیه هست ک در o(1 مین رو حذف میکنیم بعد دوباره یک عنصر دیگه به هیپ اضافه میکنیم باlogk هیپ رو شکل میدیم به تعداد عناصرت بجز ۳ باید این کارو کنی یعنی n-3بار یعنی (n-3) بار ک هر کدوم logk هزینه داره ک میشه nlogk
(۰۸ بهمن ۱۳۹۳ ۰۱:۵۸ ب.ظ)IT93 نوشته شده توسط:(08 بهمن ۱۳۹۳ ۰۱:۴۵ ب.ظ)shamim_70 نوشته شده توسط: اوکی من درمورد o(nبودنش توجیه شد!
ولی درباره اون فرمول نه!ک گفتین:
"به روش درخت انتخابی ک میشه
K log k+n log k
مجموع این هزینه میشه o(n log k"
n log kماله ادغام k ارایه مرتب هست!!(ک یبار دیگ هم گفتم مربوط به درخت انتخابی هست))..اون یکی چیه؟
Klogk ساخت مین هیپ اولیه هست ک در o(1 مین رو حذف میکنیم بعد دوباره یک عنصر دیگه به هیپ اضافه میکنیم باlogk هیپ رو شکل میدیم به تعداد عناصرت بجز ۳ باید این کارو کنی یعنی n-3بار یعنی (n-3) بار ک هر کدوم logk هزینه داره ک میشه nlogk
نمیدونم اصلااااا این فرمولتونو نمیتونم درک کنم!!
اینی ک شما الان توضیح دادین ساخت minheap با روش درخت اتنخابی هست!درسته؟
من اینجور فهمیدم شما میگید ادغام کردن kتا لیست مرتب با روش minheap از[tex]O(n\: \log\: k)[/tex]هست و ساخت BSTمتوازن هم با یک لیست مرتب nعضوی هم میشه[tex]O(n)[/tex]
در نتیجه:[tex]O(n) O(nlogk)=O(nlogk)[/tex]ک مرتبه خطی میشه!!
درسته؟
(۰۸ بهمن ۱۳۹۳ ۰۲:۴۱ ب.ظ)shamim_70 نوشته شده توسط:(08 بهمن ۱۳۹۳ ۰۱:۵۸ ب.ظ)IT93 نوشته شده توسط:(08 بهمن ۱۳۹۳ ۰۱:۴۵ ب.ظ)shamim_70 نوشته شده توسط: اوکی من درمورد o(nبودنش توجیه شد!
ولی درباره اون فرمول نه!ک گفتین:
"به روش درخت انتخابی ک میشه
K log k+n log k
مجموع این هزینه میشه o(n log k"
n log kماله ادغام k ارایه مرتب هست!!(ک یبار دیگ هم گفتم مربوط به درخت انتخابی هست))..اون یکی چیه؟
Klogk ساخت مین هیپ اولیه هست ک در o(1 مین رو حذف میکنیم بعد دوباره یک عنصر دیگه به هیپ اضافه میکنیم باlogk هیپ رو شکل میدیم به تعداد عناصرت بجز ۳ باید این کارو کنی یعنی n-3بار یعنی (n-3) بار ک هر کدوم logk هزینه داره ک میشه nlogk
نمیدونم اصلااااا این فرمولتونو نمیتونم درک کنم!!
اینی ک شما الان توضیح دادین ساخت minheap با روش درخت اتنخابی هست!درسته؟
من اینجور فهمیدم شما میگید ادغام کردن kتا لیست مرتب با روش minheap از[tex]O(n\: \log\: k)[/tex]هست و ساخت BSTمتوازن هم با یک لیست مرتب nعضوی هم میشه[tex]O(n)[/tex]
در نتیجه:[tex]O(n) O(nlogk)=O(nlogk)[/tex]ک مرتبه خطی میشه!!
درسته؟
خطی بودن ک خطی هست! nlogn هم خطی هست . N هم خطی هست! Nlogk هم خطی هست و.... خطی بودن و بیخیال شید اصلا معیار خوبی نیست اینجا
چیزی ک خطی نیست nبه توان x هست ک نمایی هست
ببیند ۴n بزرگتر از n هست یا نه ? اصولا ۱ بزرگتر از ۴ هست پس ۴n بزرگتر از n هست ! اما همه اینها o(n هستن اما این ب این معنی نیست ک مساوی اند اما در یک حد و حدود هستن
Nk هم چون k ی ضریب هست از n بزرگترها اما باز o(n هست !! و چون o(n کلا کوچکتر از nlogn هست کلا nk کوچکتر هست چرا چون kضریب هست !
اونی ک تویه نوت نوشتم ی روش ساده تره اون این هیپ سخت تره ی کم ولی یکی میشه جوباشون هر دوتا o(n هستن
جدی N لوگN خطیه؟
اخرش به نتیجه رسیدین؟
اگه بلی میشه از اول روال رو تا اخر مرتب و منظم توضیح بدین؟ ممنون
(۱۰ بهمن ۱۳۹۳ ۱۰:۳۳ ب.ظ)ریحان نوشته شده توسط: جدی N لوگN خطیه؟
اخرش به نتیجه رسیدین؟
اگه بلی میشه از اول روال رو تا اخر مرتب و منظم توضیح بدین؟ ممنون
سرکار خانوم nlogn و n نسبت بهم بصورت چند جمله ای بزرگتر نیستن پس بزرگتر است ولی نه بصورت چند جمله ای!
یاین ک خطی هست یا نه کافیه ی حلقه for بنویسید اعداد رو بر اساس nlogn تولید کنید و اعداد رو اکسل بدید تا نمودار ترسیم کنه ببیند منحنی میشه یا خطی
تویه اون نوت ی روش گفته شده بصورت مرتب از اول تا اخر .مبهم هست ? کجاش دقیقا ? بگید تا توضیح بدم
مقایسه nlogn و n
![[تصویر: 331036_1077aeb66ce6a8ed70d4664c8ebe112731a33b4a.jpg]](https://img.manesht.ir/331036_1077aeb66ce6a8ed70d4664c8ebe112731a33b4a.jpg)
۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰
۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰
مقایسه nlogn , n, n^2 .
![[تصویر: 331036_9c1f37ec320f285482da85d0e78c424d06caf8d6.jpg]](https://img.manesht.ir/331036_9c1f37ec320f285482da85d0e78c424d06caf8d6.jpg)
توجه کنید ک این سه تا نمودار هست در واقع nlogn و n روی هم افتادن (خاکستری و نارنجی). در مقایسه با فاصله شون با n به توان ۲ ک ابی هست.
اینم کد:
![[تصویر: 331036_b5ce47f0a57f8ab4b16e2aedd9b055f6345f84a7.jpg]](https://img.manesht.ir/331036_b5ce47f0a57f8ab4b16e2aedd9b055f6345f84a7.jpg)
ممنون
ممنون میشم یکی از دوستان که جواب سوال تاپیک رو کامل میدونن توضیح مختصر و منظم بفرمایند
با nlogkسه تا ارایه مرتب رو ادغام میکنیم میشه ی ارایه مرتب بعد با روش میانه گیری (روشی دوست عزیز زحمت کشیدن با شکل توضیح دادن)هربار میانه رو پیدا میکنی(چون ارایه مرتب هست پیدا کرد میانه و گذاشتنش توی ریشه از مرتبه ۱هس)پس nتا عنصرو میشه با مرتبه n(ک البته بیشتر از این مقدار میشه!)BSTرو ساخت !BSTهم متوازن درمیاد!
(۱۱ بهمن ۱۳۹۳ ۰۸:۱۱ ب.ظ)ریحان نوشته شده توسط: ممنون
ممنون میشم یکی از دوستان که جواب سوال تاپیک رو کامل میدونن توضیح مختصر و منظم بفرمایند
سلام
همونطور که بچه ها گفتن با ادغام این سه آرایه مرتب با مرتبه nlog3 و میانه گیری از مرتبه n میشه این کار رو در کمتر از nlogn انجام داد درصورتی که سوال گفته حداقل هزینه لازم برای این کار nlogn هست
تا این حد بدونین کافیه و لازم نیس خودتونو گیج کنید دوست عزیز
موفق باشین ر:
ممنون.البته ادغام ۳ ارایه مرتب با N عنصر از مرتبه N هست چون فقط مقایسه داریم.
بعد فکر کنم اومدن با جستجوی دودویی میانه پیدا میکنن و میذارن ریشه و به ترتیب درخت کامل جلو میرن که , و ریشه هست جمع اندیس اول و اخره تقسیم ۲ و چون N تا عنصره و ریشه ها کمتره N تاهستن پیدا کردن ریشه ها میشه از مرتبه کمتره N درسته؟
اصن لوگN نداریم چون فقط میانه ها رو میخوایم.هر میانه بامرتبه ۱
درنهایت با مرتبه N تعداد Nعنصر را در درخت BST متوازن درج میکنیم...درسته؟
دوستان خوب جواب بدید نتیجه گیری شه..
بیخیال من هماهنگ کردم نیاد این سوالد
کافیه همین ک بدانید اگه ارایه بدن یعنی اعداد دونه دونه وارد نشن !هم bstهم heapرو میشه تویه n ساخت حفظ کنید بره
سلام چون اگه عناصر از قبل داشته باشی میتونی اول میانه عناصر با (۱)o میانه رو پیدا کنی بعد اول عنصر وسط بذاری ریشه حالا میانه قرار گرفته ریشه و رابطه بازگشتی میشه : T(n) = 2T(n/2)+1 که میشه از مرتبه n .
n\2 واسه عناصر چپ راست . ۱ هم واسه بدست آوردن میانه