۰
subtitle
ارسال: #۱
  
الگوریتم پیدا کردن کلیدها در بازه a تا b در BTS
سلام
سوال مربوطه به سوال ۴۹، ۱۰۰ درصد اول پارسه ۹۵/ با چه الگوریتمی میشه این کلیدها رو در (O(n+h پیدا کرد ؟ در جواب سوال تنها به مرتبه اجراییش که (O(n+h هست اشاره کرده و مبهم پاسخ داده. h ارتفاع و n تعدادکلید ها در بازه a تا b هست.
تشکر
سوال مربوطه به سوال ۴۹، ۱۰۰ درصد اول پارسه ۹۵/ با چه الگوریتمی میشه این کلیدها رو در (O(n+h پیدا کرد ؟ در جواب سوال تنها به مرتبه اجراییش که (O(n+h هست اشاره کرده و مبهم پاسخ داده. h ارتفاع و n تعدادکلید ها در بازه a تا b هست.
تشکر
۲
ارسال: #۲
  
RE: الگوریتم پیدا کردن کلیدها در بازه a تا b در BTS
سلام. وقت بخیر.
میتونیم با (O(h اولین عنصر بزرگترمساوی a رو پیدا کنیم. بعد شروع به پیمایش میان ترتیب کنیم تا زمانی که عنصر کنونی کوچکتر مساوی b باشه. پیچیدگی پیمایش میان ترتیب به ازای nهای کوچیک (تعداد کمی عدد بین a تا b باشه) از مرتبه (O(h و برای nهای بزرگ از مرتبه (O(n میشه.
میتونیم با (O(h اولین عنصر بزرگترمساوی a رو پیدا کنیم. بعد شروع به پیمایش میان ترتیب کنیم تا زمانی که عنصر کنونی کوچکتر مساوی b باشه. پیچیدگی پیمایش میان ترتیب به ازای nهای کوچیک (تعداد کمی عدد بین a تا b باشه) از مرتبه (O(h و برای nهای بزرگ از مرتبه (O(n میشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close