Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:الگوریتم ها:سوال ۱

سوال ۱

  1. مرتبه زمانی رابطه‌های بازگشتی زیر را محاسبه کرده و آنها را با هم مقایسه کنید.
    • T(n)=nT(n/2)+1
    • T(n)=2T(n1)+2T(n2)++2T(2)+2T(1)
  2. مرتبه زمانی رابطه بازگشتی زیر را محاسبه کنید:
    • T(n)=T(n/4)+log3n

در هر دو قسمت برای اثبات جواب لازم نیست از روش جایگذاری استفاده کنید، اما باید روش اثبات‌تان در حد قابل قبولی دقیق باشد.


ابزار صفحه