مرتب سازی n عدد متمایز در بازه ی [tex]\langle1...n^{\log n}\rangle[/tex] از چه مرتبه ای میشه ؟
ممنون میشم برای حل سوال راهنمایی کنید
(۱۱ اسفند ۱۳۹۵ ۰۲:۲۲ ق.ظ)samanbeigmiri نوشته شده توسط: سلام
من توی قدسی اینو ندیدم
اما فک کنم بشه همون مرتب سازی رادیکس سورت که از مرتبه ی n هست.
البته باید این بازه تغییر داده بشه که بصورت توان هایی از دو در بیادش یعنی کمی دستکاری کنید بازه رو.
سوال مربوط به کتاب داده ساختار ها و مبانی الگوریتم دکتر قدسی هستش . در صورت سوال بطور کاملتر ذکر شده اثبات کنید این کار در مرتبه [tex]O(nloglogn)[/tex] قابل انجام هستش نه [tex]O(n)[/tex]
(۱۲ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)arash691 نوشته شده توسط: اثبات کنید این کار در مرتبه [tex]O(nloglogn)[/tex] قابل انجام هستش نه [tex]O(n)[/tex]
سلام . و وقت بخیر ( طبق صورت سوال هر عدد حداکثر [tex]\log n[/tex] بار تکرار شده .)
با عدد داده شده یک [tex]BST[/tex] متوازن می سازیم و در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت [tex]\log(\log n)[/tex] میشه چون ما [tex]Logn[/tex] عدد داریم مرتبه ساخت برابر [tex]nloglogn[/tex] است سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل [tex]O(n+nloglogn)=O(nloglogn)[/tex] میشه
(۱۳ اسفند ۱۳۹۵ ۱۲:۲۹ ق.ظ)alireza01 نوشته شده توسط:سلام(12 اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)arash691 نوشته شده توسط: اثبات کنید این کار در مرتبه [tex]O(nloglogn)[/tex] قابل انجام هستش نه [tex]O(n)[/tex]
سلام . و وقت بخیر ( طبق صورت سوال هر عدد حداکثر [tex]\log n[/tex] بار تکرار شده .)
با عدد داده شده یک [tex]BST[/tex] متوازن می سازیم و در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت [tex]\log(\log n)[/tex] میشه چون ما [tex]Logn[/tex] عدد داریم مرتبه ساخت برابر [tex]nloglogn[/tex] است سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل [tex]O(n+nloglogn)=O(nloglogn)[/tex] میشه
در صورت سوال چیزی درباره تکرار گفته نشده چگونه به این نتیجه رسیدید که هر عدد حداکثر logn بار تکرار شده؟
و اینکه در متن جوابتان گفتید که "چون ما logn عدد داریم مرتبه ..." در حالی که در سوال ذکر شده n عدد متمایز دارم؟
تلاش های زیادی برای رسیدن به این مرتبه در طی سالیان اخیر انجام شده که نمی توان این جا در چند سطر عنوان کرد می توانید sorting n number in [tex]O(nlglgn)[/tex]را جستجو کنید چندین مقاله در این باره وجود داره. باروش های متفاوت. و گاها سخت و فراتر از دانش من.