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

دو سوال از مرتبه ها

ارسال:
  

mahdikoochooloo پرسیده:

دو سوال از مرتبه ها

به نام خدا
سلام

رفقا دو تا سوال داشتم‌:
۱- T(n) = T(n-2) +lgn جوابش چی می شه؟ من دیدم نوشته بود nlgn اما چرا؟

۲- اگر پیچیدگی الگوریتمی به صورت N^2+ N^2+N^2 ... باشه آیا جواب می شه theta(n^3 یا می شه Theta(n^2 ؟

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: دو سوال از مرتبه ها

به نظرم میشه اینجوری حلشون کرد

در مورد سوال اولتتون دنباله‌ی حاصله به این شکل میشه

[tex]Lgn lg(n-2) lg(n-4) ...=lg(n(n-2)(n-4)...)\approx lg(n^{n})=nlgn[/tex]


در مورد سوال ۲ اگه تعداد تکرار این N^2‌ها N تا باشه N^3 میشه

[tex]n^2 n^2 ...=n^2(1 1 1 ...)=n^2(n)=n^3[/tex]



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مقایسه مرتب بودن مرتبه های زمانی csharpisatechnology ۱۶ ۵,۹۲۱ ۲۵ دى ۱۳۹۱ ۰۳:۰۶ ب.ظ
آخرین ارسال: csharpisatechnology
  یافتن مولفه های همبند گراف جهتدار ، باچه روش و چه مرتبه ای؟ Masoud05 ۲ ۴,۱۵۸ ۲۰ دى ۱۳۹۱ ۰۸:۳۲ ب.ظ
آخرین ارسال: reza_d500
  مرتبه زمانی ۲ haamidit ۹ ۴,۲۸۵ ۰۹ آذر ۱۳۹۱ ۰۸:۱۸ ب.ظ
آخرین ارسال: farhadk
  مرتبه زمانی haamidit ۶ ۳,۳۸۸ ۰۶ آذر ۱۳۹۱ ۰۱:۰۴ ق.ظ
آخرین ارسال: Amir V
Smile طراحی الگوریتم - مرتبه زمانی kiantamar ۱۲ ۱۱,۷۶۱ ۰۱ آبان ۱۳۹۱ ۰۵:۱۷ ق.ظ
آخرین ارسال: csharpisatechnology
  محاسبه مرتبه اجرایی این کدها one hacker alone ۷ ۳,۹۰۰ ۲۷ خرداد ۱۳۹۱ ۱۰:۴۶ ب.ظ
آخرین ارسال: riga
  سوالی در زمینه مرتبه اجرایی unicornux ۲ ۱,۴۸۷ ۲۰ خرداد ۱۳۹۱ ۱۰:۰۲ ق.ظ
آخرین ارسال: a.hooshmand
  مرتبه اجرایی این الگوریتم؟ fa_karoon ۳ ۲,۶۵۳ ۲۳ فروردین ۱۳۹۱ ۱۰:۵۱ ب.ظ
آخرین ارسال: fa_karoon
  [نکات] کارآیی ، تحلیل و مرتبه الگوریتم ها - روابط بازگشتی Masoud05 ۲۲ ۱۲,۵۲۲ ۱۶ فروردین ۱۳۹۱ ۰۱:۲۵ ق.ظ
آخرین ارسال: Masoud05
  مرتبه اجرایی تست vijay ۱ ۱,۳۷۰ ۲۳ دى ۱۳۹۰ ۰۸:۱۴ ب.ظ
آخرین ارسال: homa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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