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

(۱) تحلیل زمان اجرا

ارسال:
  

- rasool - پرسیده:

Star (۱) تحلیل زمان اجرا

الله

می خواستم در مورد این نکته ظریف بپرسم که دقیقا تفاوت مرتبه(هزینه) اجرا بین دو تابع بازگشتی (f(n)=n+f(n-1 و (T(n)=n+T(n-1 چیست ؟
( در اولی می شه n و در دومی می شه n^2 )


متشکرم.

۲
ارسال:
  

Masoud05 پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

(۱۰ مهر ۱۳۹۰ ۰۶:۱۶ ب.ظ)yaali نوشته شده توسط:  الله

می خواستم در مورد این نکته ظریف بپرسم که دقیقا تفاوت بین این دو چیست؟

مثلا در مورد تابع بازگشتی (f(n)=n+f(n-1 یا (T(n)=n+T(n-1 در جایی می خوندم که زمان اجرا n و مرتبه اجرا n^2 هستش.

همچنین درمورد تابع بازگشتی فاکتوریل که اگه زمان اجرا رو بخواهیم می شه n‌، چون n بار فراخوانی می شه اما اگه با روش جایگزینی مرتبه‌ی آن را حساب کنیم
می شه n فاکتوریل.
اینکه در سوال از ما کدوم رو می خواهند از کجا بفهمیم؟

البته فکر کنم بیشتر جاها یکسان باشند.

نظر شما چیه؟

متشکرم.

دوست عزیز فکر کنم شما دارید کپی تست‌ها ساختمان رو مینویسید‌، اگه اینطوره باید بگم:
اونی که تابعش (f(nهست . این در واقع خود الگوریتم هست( خود شبه کد )پس اینجا برای مقدار n که توی رابطه هست زمانی نیاز نیست صرف بشه . اما اونی که (T(n هست برای خود مقدار n یعنی n عمل پس به زمان n نیاز داره. امیدورام متوجه منظورم شده باشه( f یه رابطه ساده هست مثل جمع اما T توی اینجا یه رابطه بازگشتی هست )
عین تست رو بزار تا برات بگم چی به چیه

ارسال:
  

- rasool - پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

متشکرم از راهنماییتون.
یعنی شما فقط از لفظ f یا T متوجه می شوید ؟
چون گاهی اصلا شبه کد را نداده و آمده رابطه بازگشتی را با حرف f نوشته.
و یا ممکنه شبه کد باشه ولی از حرف T استفاده کرده باشه !؟

(۱۰ مهر ۱۳۹۰ ۱۰:۱۷ ب.ظ)Masoud05 نوشته شده توسط:  دوست عزیز فکر کنم شما دارید کپی تست‌ها ساختمان رو مینویسید‌، اگه اینطوره باید بگم:
ببخشید متوجه این فرمایشتون نشدم !
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

- rasool - پاسخ داده:

(۱) تفاوت زمان اجرا با مرتبه اجرا

بله. بیشتر منظورم همون دو تا تست بود.

ارسال:
  

Masoud05 پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

(۱۰ مهر ۱۳۹۰ ۱۱:۲۲ ب.ظ)yaali نوشته شده توسط:  بله. بیشتر منظورم همون دو تا تست بود.
عکسش رو بزار تا بگم چی به چیه
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

- rasool - پاسخ داده:

(۱) تفاوت زمان اجرا با مرتبه اجرا

سوالات رو پیوست کردم.
دوتا مال کتاب آقای مقسمی و دوتا مال کتاب آقای یوسفی که با نام عکس‌ها مشخص کرده ام.
اما جواب این بزرگواران:

آقای یوسفی:
سوال اول‌: n
سوال دوم‌: n^2

آقای مقسمی:
سوال اول:n
سوال دوم: n^2


فایل‌(های) پیوست شده


ارسال:
  

Masoud05 پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

(۱۰ مهر ۱۳۹۰ ۱۱:۴۴ ب.ظ)yaali نوشته شده توسط:  سوالات رو پیوست کردم.
دوتا مال کتاب آقای مقسمی و دوتا مال کتاب آقای یوسفی که با نام عکس‌ها مشخص کرده ام.
اما جواب این بزرگواران:

آقای یوسفی:
سوال اول‌: n
سوال دوم‌: n^2

آقای مقسمی:
سوال اول:n
سوال دوم: n^2

خودم فکر می کنم بحث سر کلمات زمان اجرا و مرتبه اجرا هستش.

ببین در سوال اول یک رابطه داری که توی اون n یک مقدار ثابت هست یعنی توی هزینه‌ها اعمال نمیشه( در واقع برای محاسبه اون زمانی نیاز نیست چون خودش یه مقداره مثل اینکه بگیم فلان متغیر مقدارش اینه )پس شما فقط باید (T(n-1 رو n بار حساب کنی( مثل یه حلقه for )که زمانش میشه n
اما در سوال بعدی دیگه رابطه بازگشتی داریم و اون n دیگه بمعنای یه عدد ثابت نیست بلکه بمعنای اینکه به ازای (T(n-1 باید ۱-n تا کار صورت بگیره یعنی میشه جمع اعداد۱ تا ۱-n که مرتبه اون n^2 هست . بعارت دیگه‌:
n-1 <=== n-1 کار
۲-n-2 <=== n کار
.
.
.
۱====> 1 کار
مجموع کارها توانی از ۲ هست.
حالا یه بار دیگه تست‌ها رو بررسی کن.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

- rasool - پاسخ داده:

(۱) تفاوت زمان اجرا با مرتبه اجرا

لطفا در مورد تابع بازگشتی فاکتوریل هم توضیح بفرمایید.

ارسال:
  

Masoud05 پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

(۱۱ مهر ۱۳۹۰ ۱۲:۰۵ ق.ظ)yaali نوشته شده توسط:  لطفا در مورد تابع بازگشتی فاکتوریل هم توضیح بفرمایید:
اینو من فهمیدم‌: اگه زمان اجرا رو بخواهیم می شه n‌، چون n بار فراخوانی می شه اما اگه با روش جایگزینی مرتبه‌ی آن را حساب کنیم می شه n فاکتوریل.

اما از کجا بدونیم منظور طراح کدوم یکی هستش؟

ببین اینم مثل بالایه‌:
الگوریتم‌: [tex]f(n) = n * f (n-1) [/tex]
پس اگه بخواهی مرتبه اونو حساب کنی‌، چون خط فوق یک کد هست و نه یک رابطه بازگشتی مقدار خود n، یعنی یه مقدار ثابت‌، پس مثل اینه که یک for داری با زمان n
اما برای مقدارش شما خود n های بالا رو حساب میکنی( که حساب کردن n در زمان ثابت صورت میگیره یعنی مرتبه اون ۱ هست )یعنی همون مقدار فاکتوریل.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

لهمشد پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

ممنون از پاسخ بسیار خوب آقای مسعود .من خودم قبلا این سوال رو درک نمی کردم و با پاسخ خوبتون باعث میشه هر شبهه ای برطرف بشه . به هر ترتیب ممنون

ارسال: #۱۱
  

Masoud05 پاسخ داده:

RE: (1) تفاوت زمان اجرا با مرتبه اجرا

(۱۱ مهر ۱۳۹۰ ۰۳:۵۰ ب.ظ)لهمشد نوشته شده توسط:  ممنون از پاسخ بسیار خوب آقای مسعود .من خودم قبلا این سوال رو درک نمی کردم و با پاسخ خوبتون باعث میشه هر شبهه ای برطرف بشه . به هر ترتیب ممنون
خواهش میکنم . خوشحال میشم اگه بتونم به کسی کمک کنم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۲
  

mojgan پاسخ داده:

RE: (۱) تحلیل زمان اجرا

سلام
واقعا مرسی که جواب دادین با حوصله
ولی من هنوز نفهمیدم و اصلا سوال خودمم بوده
اگه می تونید یا یه مثال دیگه توضیح بدبد فرق مرتبه و زمان اجرا
ممنونHuh



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۴ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
  استخدام کارشناس تحلیل داده zeinab_IT ۰ ۱,۰۰۴ ۱۷ بهمن ۱۴۰۰ ۱۲:۳۱ ب.ظ
آخرین ارسال: zeinab_IT
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۴۷۳ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  بهترین گرایش برای موقعیت شغلی تحلیل سیستم shahabkarimi00 ۳ ۵,۵۱۲ ۰۹ آذر ۱۳۹۹ ۰۳:۳۵ ب.ظ
آخرین ارسال: mohammadasadi1
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۲,۵۹۱ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  خواص محیط برای عامل سیستم تحلیل تصاویر پزشکی Ali1991khe ۶ ۵,۱۲۵ ۰۴ مهر ۱۳۹۹ ۰۸:۳۲ ق.ظ
آخرین ارسال: Ali1991khe
  اجرای نرم افزار ویندوز در اندروید elecomco ۰ ۲,۷۸۶ ۰۴ خرداد ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: elecomco
  در مصاحبه کارشناس تحلیل گر سیستم چه می پرسند؟ سیما ۱۹۵۶ ۲۸ ۴۳,۵۳۵ ۱۳ اسفند ۱۳۹۸ ۱۱:۴۹ ق.ظ
آخرین ارسال: alma1988
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۱,۹۰۷ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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