(۱۲ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)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]را جستجو کنید چندین مقاله در این باره وجود داره. باروش های متفاوت. و گاها سخت و فراتر از دانش من.