چ سخته نوشتن تویه این نوت ! بد خط شد :دی



اگه غلط هست یا سوال بود باز در خدمتیم[/php]

البته با اون یکی روش ک بالا گفتم میشه در کمتر هم حل ش کرد ک میشه nlogk ک باز اینم از nlogn کوچکتره

با nlogkسه تا ارایه مرتب رو ادغام میکنیم میشه ی ارایه مرتب بعد با روش میانه گیری (روشی دوست عزیز زحمت کشیدن با شکل توضیح دادن)هربار میانه رو پیدا میکنی(چون ارایه مرتب هست پیدا کرد میانه و گذاشتنش توی ریشه از مرتبه ۱هس)پس nتا عنصرو میشه با مرتبه n(ک البته بیشتر از این مقدار میشه!)BSTرو ساخت !BSTهم متوازن درمیاد!

برای یه عنصر ، درج در 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 log k+n log k

اینجا k=3 دیگه، میشه خطی.

(۰۷ بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)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

اوه.روانی شدم
کمک

ادغام kارایه مرتب با n عنصر با روشی شما گفتید میشه nk...ولی اگ با درخت انتخابی حلش کنیم میشه حداگثر n log k!!که بهتر از روش اوله!

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

فک کنم منظورتون اینه هردفعه با o(1) عنصر میانه رو پیدامی کنید میزارید ریشه واینکارو چون n بار انجام میدین میشه o(n)..!!درسته؟؟

(۰۸ بهمن ۱۳۹۳ ۱۱:۰۵ ق.ظ)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




۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰
۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰


مقایسه nlogn , n, n^2 .


توجه کنید ک این سه تا نمودار هست در واقع nlogn و n روی هم افتادن (خاکستری و نارنجی). در مقایسه با فاصله شون با n به توان ۲ ک ابی هست.


اینم کد:

ممنون

ممنون میشم یکی از دوستان که جواب سوال تاپیک رو کامل میدونن توضیح مختصر و منظم بفرمایند

(۱۱ بهمن ۱۳۹۳ ۰۸:۱۱ ب.ظ)ریحان نوشته شده توسط:  ممنون

ممنون میشم یکی از دوستان که جواب سوال تاپیک رو کامل میدونن توضیح مختصر و منظم بفرمایند

سلام
همونطور که بچه ها گفتن با ادغام این سه آرایه مرتب با مرتبه nlog3 و میانه گیری از مرتبه n میشه این کار رو در کمتر از nlogn انجام داد درصورتی که سوال گفته حداقل هزینه لازم برای این کار nlogn هست
تا این حد بدونین کافیه و لازم نیس خودتونو گیج کنید دوست عزیز
موفق باشین ر:

ممنون.البته ادغام ۳ ارایه مرتب با N عنصر از مرتبه N هست چون فقط مقایسه داریم.
بعد فکر کنم اومدن با جستجوی دودویی میانه پیدا میکنن و میذارن ریشه و به ترتیب درخت کامل جلو میرن که , و ریشه هست جمع اندیس اول و اخره تقسیم ۲ و چون N تا عنصره و ریشه ها کمتره N تاهستن پیدا کردن ریشه ها میشه از مرتبه کمتره N درسته؟
اصن لوگN نداریم چون فقط میانه ها رو میخوایم.هر میانه بامرتبه ۱

درنهایت با مرتبه N تعداد Nعنصر را در درخت BST متوازن درج میکنیم...درسته؟

دوستان خوب جواب بدید نتیجه گیری شه..

بیخیال من هماهنگ کردم نیاد این سوالد

کافیه همین ک بدانید اگه ارایه بدن یعنی اعداد دونه دونه وارد نشن !هم bstهم heapرو میشه تویه n ساخت حفظ کنید بره

(۱۵ بهمن ۱۳۹۳ ۰۸:۱۵ ب.ظ)IT93 نوشته شده توسط:  
بیخیال من هماهنگ کردم نیاد این سوالد

کافیه همین ک بدانید اگه ارایه بدن یعنی اعداد دونه دونه وارد نشن !هم bstهم heapرو میشه تویه n ساخت حفظ کنید بره

دستتون درد نکنه

سلام چون اگه عناصر از قبل داشته باشی میتونی اول میانه عناصر با (۱)o میانه رو پیدا کنی بعد اول عنصر وسط بذاری ریشه حالا میانه قرار گرفته ریشه و رابطه بازگشتی میشه : T(n) = 2T(n/2)+1 که میشه از مرتبه n .
n\2 واسه عناصر چپ راست . ۱ هم واسه بدست آوردن میانه