سلام
سوال مربوطه به سوال ۴۹، ۱۰۰ درصد اول پارسه ۹۵/ با چه الگوریتمی میشه این کلیدها رو در (O(n+h پیدا کرد ؟ در جواب سوال تنها به مرتبه اجراییش که (O(n+h هست اشاره کرده و مبهم پاسخ داده. h ارتفاع و n تعدادکلید ها در بازه a تا b هست.
تشکر
سلام. وقت بخیر.
میتونیم با (O(h اولین عنصر بزرگترمساوی a رو پیدا کنیم. بعد شروع به پیمایش میان ترتیب کنیم تا زمانی که عنصر کنونی کوچکتر مساوی b باشه. پیچیدگی پیمایش میان ترتیب به ازای nهای کوچیک (تعداد کمی عدد بین a تا b باشه) از مرتبه (O(h و برای nهای بزرگ از مرتبه (O(n میشه.