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

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

ارسال:
  

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