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

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

ارسال:
  

- 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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  خواص محیط برای عامل سیستم تحلیل تصاویر پزشکی Ali1991khe ۶ ۲۰۵ ۰۴ مهر ۱۳۹۹ ۰۸:۳۲ ق.ظ
آخرین ارسال: Ali1991khe
  در مصاحبه کارشناس تحلیل گر سیستم چه می پرسند؟ سیما ۱۹۵۶ ۲۸ ۲۵,۴۲۵ ۱۳ اسفند ۱۳۹۸ ۱۱:۴۹ ق.ظ
آخرین ارسال: alma1988
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۴۰۶ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
  منابع تخصصی شغل تحلیل گر سیستم Hamedudk ۱ ۸۹۷ ۰۷ آبان ۱۳۹۸ ۰۱:۰۸ ق.ظ
آخرین ارسال: marvelous
  بهترین منابع برای تحلیل اقتصادی کدامند؟ hoseyn9999so ۰ ۵۳۳ ۱۶ مهر ۱۳۹۸ ۰۶:۴۵ ق.ظ
آخرین ارسال: hoseyn9999so
Exclamation زمان برگزاری کنکور ارشد ۹۸ به تعویق افتاد elect ۲ ۷۵۴ ۱۳ مهر ۱۳۹۸ ۰۵:۲۴ ب.ظ
آخرین ارسال: saharfarhang
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۵,۴۱۸ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20
  در مصاحبه کارشناس تحلیل گر سیستم چه می پرسند؟ manamsaeid ۱ ۱,۱۹۰ ۰۱ مهر ۱۳۹۷ ۱۲:۴۳ ق.ظ
آخرین ارسال: negarin_
  تعیین زمان سفارت کشور فرانسه zpv1234 ۰ ۷۹۳ ۲۱ شهریور ۱۳۹۷ ۰۱:۴۸ ب.ظ
آخرین ارسال: zpv1234
  الگوریتم SRT زمانبندی کوتاه ترین زمان باقی مانده Happiness.72 ۶ ۸,۱۸۷ ۲۴ خرداد ۱۳۹۷ ۰۷:۵۷ ب.ظ
آخرین ارسال: amirjo0on

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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