زمان کنونی: ۳۱ فروردین ۱۴۰۳, ۱۰:۰۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتبه زمانی سوال کنکور ۹۴

ارسال:
  

yotab2013 پرسیده:

مرتبه زمانی سوال کنکور ۹۴

سلام دوستان
مرتبه این الگوریتم رو کسی میدونه چطور به دست میاد؟
T(n)=t(log n)+O(1)
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

msour44 پاسخ داده:

RE: مرتبه زمانی سوال کنکور ۹۴

سلام
برای حل این تست باید با تابع لگاریتمی تکراری اشنایی داشته باشید
[tex]\lg^{\ast}n=\min\{i\ge0\: :\: \lg^{(i)}n\le1\}[/tex]
اگر به رابطه بازگشتی [tex]T(n)[/tex]نگاه کنید هر بار از ارگومان رابطه لگاریتم گرفته می شود تا زمانی که مقدار ارگومان به یک برسه (برای این تست شرط توقف رابطه به ازای ورودی یک که مقدار یک تولید می کند می باشد)رابطه تکرار می شه این همون [tex]\lg^{_{\ast}}n[/tex] .یعنی تعداد تکرار تا رسیدن به شرط توقف برابر با تعداد باری که لگاریتم می گیرم تا به یک برسیم که هزینه هر تکرار هم ثابت است پس رابطه بازگشتی از مزتبه [tex]O(\lg^{\ast}n)[/tex]
اگر متوجه نشدید در بعضی منابع[tex]\lg^{\ast}n[/tex] به صورت زیر هم تعریف می شود
[tex]\lg^{\ast}n=0\: \: \: \: if\: \: n\le1[/tex]
[tex]\lg^{\ast}n=1+\lg^{\ast}(\lg n)\: \: \: if\: \: n>1[/tex]
حالا به شباهت تابع [tex]\lg^{\ast}[/tex] و T دقت کنید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۹۰۶ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۵۹ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۶۶ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۳۲۲ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۳۰۶ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۵۷۷ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۴۴۲ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۳,۳۱۴ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  مباحث آزاد آزمون دکترا ۹۸ (قبل ار کنکور-بعد از کنکور) taha.maten ۰ ۲,۱۱۷ ۲۴ بهمن ۱۳۹۷ ۱۲:۴۶ ب.ظ
آخرین ارسال: taha.maten
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۵۲۸ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close