دوستان مرتبه ی درج ۳ تا لیست مرتب در درخت bst چی میشه؟
توی نصیر نوشته با مرتبه خطی مرتب میشه که خب قبول اما بعد گفته با مرتبه n در درخت جستجوی دودویی درجش میکنیم من با این مشکل دارم مگه درج در BST از مرتبه ی Nh نیست برای n عنصر؟ یعنی nبه توان ۲ ...... یا......n لوگ n ?
برای یه عنصر ، درج در BST در بدترین حالت از مرتبه n هست حالا اگه n عنصر داشته باشیم و یکی یکی درج کنیم ،بدترین حالت زمانی است که مرتب باشند(صعودی یا نزولی) که میشه n به توان دو ، حالت میانگین هم N در لگارتیم n هست.
میدونم اما سوالمو متوجه شدید؟ نصیر گفته ساخت BST با N عنصر از مرتبه N است یعنی خطیه؟...چرا؟
ظاهرا بستگی به این داره که عمل اصلی رو چی در نظر بگیرید
عمل اصلی همون درج n عنصره
عمق درخت توو حالت متوسط log nهست چجوری nتا رو درج کنی میشه مرتبهn?!!!!! سوالش دقیقا چی بوده؟!!
سوال it سال ۹۱
ایا این سوال غلطه؟
اگر ۳ ارایه مرتب از n عدد داشته باشیم در مدل مقایسه ای ساخت یک درخت جستجوی دودویی متوازن به هزینه ی n لوگ n نیاز دارد.
پاسخ مدرسان اینه که غلظه زیرا
مرتبش میشه لوگ n
چرا؟
سوالت منو از تووی تخت خواب کشید بیرون
قسمت اول سوال ک مشخصه ادغامkلیست مرتب ک مجنوع عناصرش nتا هست میشه از مرتبهn
قسمت بعد توجه کن نگفتهbstفقط!گفته bstمتوازن.این یعنی چی؟یعنی حالا ک تو ارایه مرتب شده ای داره از ادعام اون ۳تا لیست اگ بخوای بشیوه bstبری جلو درختت میشه مورب!چون ارایه ت مرتبه!پس اینجا مطمینیاز مرتبهn^2نیس..پس دونه دونه تو ارایه درج نکرده .فک کنم میانه رو بامرتبه ۱پیدا کرده گذاشته ریشه بعد زیردرخت چپ و راستم بهمین شکل بصورت بازگشتی رفته جلو(البته با حفظ خاصیت bst)
حالا اینکارو ب اندازهlog nتکرار میکنه چون خودش گفته avlباشه ارتفاع avlهم log n.
حالا بین مرتبهnو logn مرتبهnمیشه!(انکاری درج avlداری انجام میدی ولی با حفظ خاصیتbst)
ببخش طولانیم شد اصلا هم مطمین نیستم اینی گفتم چقد درسته!
منتظر باش بقیم جواب بدن
خخخخ اینا رو خونده بودم، یادم رفته
فقط در این حد میدونم که مرتبه ساخت با k تا لیست مرتب میشه n log k که log3 میشه ۱ و مرتبه میشه n که خطی میشه
فکر کنید اگه دلیلش رو نفهمیدید بگین برم نگاه کنم ببینم اصلا اشتباهی نگفته باشم یه وقتی
۳تا ارایه رو نمیشه تویه n ادغام کرد!
دوتا ارایه رو میشه تویهn-1 ادغام کرد ک میشه n
سه تا ارایه رو به دو روش میشه ادغام کرد
یک
N(k-1 ک میشه nk
دو
به روش درخت انتخابی ک میشه
K log k+n log k
بعدش تویه n میشه bst رو ساخت و تویه n دوباره میشه با روش inorder پیشاپیش کد ک حاصل میشه صعودی مرتب
چون مرتب هست درخت ی وری میشه ولی میشه به روش جست و جوی باینری ک mid رو پیدا میکنه اگه mid و بذاری ریشه درخت متوازن میشه حاصلش مثل avl نیست ولی متوازن هست ک میشهlog nبار (منظورم ارتفاع درخته)
مجموع این هزینه میشه o(n log k
(۰۷ بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)IT93 نوشته شده توسط: ۳تا ارایه رو نمیشه تویه n ادغام کرد!اینجا k=3 دیگه، میشه خطی.
به روش درخت انتخابی ک میشه
K log k+n log k
(۰۷ بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)IT93 نوشته شده توسط: ۳تا ارایه رو نمیشه تویه n ادغام کرد!شما زخمت کشیدین توضیح دادین و نامنظم گفتین متوجه نشدم.
دوتا ارایه رو میشه تویهn-1 ادغام کرد ک میشه n
سه تا ارایه رو به دو روش میشه ادغام کرد
یک
N(k-1 ک میشه nk
دو
به روش درخت انتخابی ک میشه
K log k+n log k
بعدش تویه n میشه bst رو ساخت و تویه n دوباره میشه با روش inorder پیشاپیش کد ک حاصل میشه صعودی مرتب
چون مرتب هست درخت ی وری میشه ولی میشه به روش جست و جوی باینری ک mid رو پیدا میکنه اگه mid و بذاری ریشه درخت متوازن میشه حاصلش مثل avl نیست ولی متوازن هست ک میشهlog nبار
مجموع این هزینه میشه o(n log k
ادغام kارایه مرتب ک مجموع اینkارایهnهس از مرتبهnlog kمیشه یعنیn log 3 ک میشه مرتبهn.
تا اینجا یک لیست مرتب داریم حالا میخوایم درج کنیم توbstولی گفته متوازن باشه...حالا ادامه شو شما بگید....
(۰۷ بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)IT93 نوشته شده توسط: ۳تا ارایه رو نمیشه تویه n ادغام کرد!
دوتا ارایه رو میشه تویهn-1 ادغام کرد ک میشه n
سه تا ارایه رو به دو روش میشه ادغام کرد
یک
N(k-1 ک میشه nk
دو
به روش درخت انتخابی ک میشه
K log k+n log k
بعدش تویه n میشه bst رو ساخت و تویه n دوباره میشه با روش inorder پیشاپیش کد ک حاصل میشه صعودی مرتب
چون مرتب هست درخت ی وری میشه ولی میشه به روش جست و جوی باینری ک mid رو پیدا میکنه اگه mid و بذاری ریشه درخت متوازن میشه حاصلش مثل avl نیست ولی متوازن هست ک میشهlog nبار
مجموع این هزینه میشه o(n log k
اوه.روانی شدم
کمک
چ سخته نوشتن تویه این نوت ! بد خط شد :دی
![[تصویر: 330117_dykjtqneoe9zwyso3lx1.jpg]](https://img.manesht.ir/330117_dykjtqneoe9zwyso3lx1.jpg)
اگه غلط هست یا سوال بود باز در خدمتیم[/php]
البته با اون یکی روش ک بالا گفتم میشه در کمتر هم حل ش کرد ک میشه nlogk ک باز اینم از nlogn کوچکتره
ادغام kارایه مرتب با n عنصر با روشی شما گفتید میشه nk...ولی اگ با درخت انتخابی حلش کنیم میشه حداگثر n log k!!که بهتر از روش اوله!
ولی متوجه نمیشم چجوری درخت رو میسازید اونم با n!!!!!!
براساس جستجو دودویی هم پیش برید برای nتا عنصردر حالت متوسط log nمقایسه لازم هست !!
فک کنم منظورتون اینه هردفعه با o(1) عنصر میانه رو پیدامی کنید میزارید ریشه واینکارو چون n بار انجام میدین میشه o(n)..!!درسته؟؟