(۱۲ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)arash691 نوشته شده توسط:  اثبات کنید این کار در مرتبه $O(nloglogn)$ قابل انجام هستش نه $O(n)$

سلام . و وقت بخیر ( طبق صورت سوال هر عدد حداکثر $\log n$ بار تکرار شده .)
با عدد داده شده یک $BST$ متوازن می سازیم و در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت $\log(\log n)$ میشه چون ما $Logn$ عدد داریم مرتبه ساخت برابر $nloglogn$ است سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل $O(n+nloglogn)=O(nloglogn)$ میشه

(۱۳ اسفند ۱۳۹۵ ۱۲:۲۹ ق.ظ)alireza01 نوشته شده توسط:  

(12 اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)arash691 نوشته شده توسط:  اثبات کنید این کار در مرتبه $O(nloglogn)$ قابل انجام هستش نه $O(n)$

سلام . و وقت بخیر ( طبق صورت سوال هر عدد حداکثر $\log n$ بار تکرار شده .)
با عدد داده شده یک $BST$ متوازن می سازیم و در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت $\log(\log n)$ میشه چون ما $Logn$ عدد داریم مرتبه ساخت برابر $nloglogn$ است سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل $O(n+nloglogn)=O(nloglogn)$ میشه

سلام
در صورت سوال چیزی درباره تکرار گفته نشده چگونه به این نتیجه رسیدید که هر عدد حداکثر logn بار تکرار شده؟
و اینکه در متن جوابتان گفتید که "چون ما logn عدد داریم مرتبه ..." در حالی که در سوال ذکر شده n عدد متمایز دارم؟
تلاش های زیادی برای رسیدن به این مرتبه در طی سالیان اخیر انجام شده که نمی توان این جا در چند سطر عنوان کرد می توانید sorting n number in $O(nlglgn)$را جستجو کنید چندین مقاله در این باره وجود داره. باروش های متفاوت. و گاها سخت و فراتر از دانش من.