(۰۸ اسفند ۱۳۹۵ ۱۲:۰۴ ق.ظ)computerman نوشته شده توسط: چرا log n
الگوریتم‌پیدا کردن عنصد بعدی و قبلی در درخت bst وابسته به ارتفاع درخت هست که حداکثر n هست
به قول خودتون LVR درخت رو باید بنویسین که با اون روشم میشه N
تنها در یک حالت خاص اگر جایگشت اعداد ورودی به صورت مرتب شده باشد بله اونموقع نظر شما درست است
چون هیچ فرضی در صورت سوال برای ورودی در نظر نگرفته شده و حالت بدترین نیز به طور خاص خواسته نشده، به همین دلیل منظور حالت میانگین الگوریتم است که از درجه logn می باشد
رجوع کنید به الگوریتم succ در درخت جستجوی دودویی کتاب ساختمان داده
سوال چهارم که نسبتا سوال سختی هست من قبلا توی سوال های آزمون برنامه نویسی گوگل دیده بودم این سوال رو
راه حل ساده این الگوریتم خب استفاده از دو تا حلقه تو در تو با زمان n^2 می باشد
چیزی که به ذهن من میاد برای این سوال ، اگر استفاده از فضای حافظه نامحدود باشه و البته نکته مهمتر اینکه علامت اعداد ورودی چی باشه دو الگوریتم به ذهنم میرسه
برای اعداد صحیح فقط مثبت میشه الگوریتمی از درجه n نوشت با الهام از الگوریتم مرتب سازی شمارشی
برای کل اعداد صحیح که احتمالا منظور سوالم همین حالته من الگوریتمی کمتر از nlogn رو نمیتونم پیدا کنم برای این مسئله
