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

مرتبه ی زمانی - IT88

ارسال:
  

Happiness.72 پرسیده:

مرتبه ی زمانی - IT88

درود و سپاس

سوال مربوط به مرتبه زمانی ای تی ۸۸ هستش . من میدونم مرتبه زمانی خط اول میشه log n بخاطر i * 2 ولی چرا دو خط بعدی که دو حلقه تو در تو هستند بخاطر j , چرا مرتبه زمانی شون میشه n که در نهایت پاسخش بشه گزینه ۳؟ مگه حلقه های تو در تو مرتبه زمانی شون نمیشه mn ؟

نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

Behnam‌ پاسخ داده:

RE: مرتبه ی زمانی - IT88

(۳۰ شهریور ۱۳۹۵ ۰۶:۵۳ ب.ظ)ITEngineering نوشته شده توسط:  درود و سپاس

سوال مربوط به مرتبه زمانی ای تی ۸۸ هستش . من میدونم مرتبه زمانی خط اول میشه log n بخاطر i * 2 ولی چرا دو خط بعدی که دو حلقه تو در تو هستند بخاطر j , چرا مرتبه زمانی شون میشه n که در نهایت پاسخش بشه گزینه ۳؟ مگه حلقه های تو در تو مرتبه زمانی شون نمیشه mn ؟

دو حلقه‌ی داخلی مستقل از حلقه‌ی بیرونی هستند و راحت‌تر میشه حساب کرد که دستور [tex]x++[/tex] چند بار حساب می‌شه. این دستور در هر بار اجرای حلقه‌ی بیرونی، به تعداد [tex]j[/tex] بار اجرا میشه که مقادیر j به ترتیب ۱، ۲، ۴، ۸، ۱۶ و .... تا n هست. پس به حاصل جمع این تعداد اجرا میشه که حاصل جمع این اعداد میشه حدود [tex]2n-1[/tex] (اگه فرض کنیم که n توانی از ۲ هست که میشه به دلخواه این فرض رو کرد ولی زیاد هم مهم نیست چون به هر حال از مرتبه‌ی n هست حاصل جمع فوق).
خلاصه در هر بار اجرای حلقه‌ی بیرونی، به تعداد ۲n-1 تا دستور اجرا میشه. دقت شود که حلقه‌ی وسطی مستقل از متغیر کنترلی حلقه‌ی اول یعنی i هست. حلقه‌ی بیرونی هم که [tex]\log(n)[/tex] بار اجرا میشه پس در نهایت میشه [tex]\log(n)\times n[/tex]

پی‌نوشت: علت اینکه مرتبه‌شون نمیشه گفت m*n این هست که متغیرهاشون به هم وابسته هستو یعنی حلقه‌ی سوم تا j میره هر بار
نقل قول این ارسال در یک پاسخ

ارسال:
  

delete4all پاسخ داده:

RE: مرتبه ی زمانی - IT88

نقل قول: دو حلقه‌ی داخلی مستقل از حلقه‌ی بیرونی هستند و راحت‌تر میشه حساب کرد که دستور [tex]x++[/tex] چند بار حساب می‌شه. این دستور در هر بار اجرای حلقه‌ی بیرونی، به تعداد [tex]j[/tex] بار اجرا میشه که مقادیر j به ترتیب ۱، ۲، ۴، ۸، ۱۶ و .... تا n هست. پس به حاصل جمع این تعداد اجرا میشه که حاصل جمع این اعداد میشه حدود [tex]2n-1[/tex] (اگه فرض کنیم که n توانی از ۲ هست که میشه به دلخواه این فرض رو کرد ولی زیاد هم مهم نیست چون به هر حال از مرتبه‌ی n هست حاصل جمع فوق).
خلاصه در هر بار اجرای حلقه‌ی بیرونی، به تعداد ۲n-1 تا دستور اجرا میشه. دقت شود که حلقه‌ی وسطی مستقل از متغیر کنترلی حلقه‌ی اول یعنی i هست. حلقه‌ی بیرونی هم که [tex]\log(n)[/tex] بار اجرا میشه پس در نهایت میشه [tex]\log(n)\times n[/tex]

پی‌نوشت: علت اینکه مرتبه‌شون نمیشه گفت m*n این هست که متغیرهاشون به هم وابسته هستو یعنی حلقه‌ی سوم تا j میره هر بار

سلام
درسته که حلقه for اول متغیرش i هست و وابستگی نداره با حلقه های داخلیش اما در هر صورت این ۳ حلقه تو در تو هستن هر سه تاشون
اولی که متغیر i هست مرتبش log n هست
و دومین حلقه با متغیر j هم مرتبش log n هست و تا اینجا میشه log n * log n
و حلقه داخلی سوم هم که مرتبش n هست پس دستور ++x باید به مقدار Log n * Log n * n بار تکرار بشه !! که میشه گزینه ۴!!
قاعدتا باید اینطور باشه چون حلقه اول مجزا نیست و ۳ حلقه تودرتو هستن

میشه لطفا بیشتر توضیح بدین
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Behnam‌ پاسخ داده:

RE: مرتبه ی زمانی - IT88

(۳۱ شهریور ۱۳۹۵ ۰۹:۴۴ ق.ظ)delete4all نوشته شده توسط:  
نقل قول: دو حلقه‌ی داخلی مستقل از حلقه‌ی بیرونی هستند و راحت‌تر میشه حساب کرد که دستور [tex]x++[/tex] چند بار حساب می‌شه. این دستور در هر بار اجرای حلقه‌ی بیرونی، به تعداد [tex]j[/tex] بار اجرا میشه که مقادیر j به ترتیب ۱، ۲، ۴، ۸، ۱۶ و .... تا n هست. پس به حاصل جمع این تعداد اجرا میشه که حاصل جمع این اعداد میشه حدود [tex]2n-1[/tex] (اگه فرض کنیم که n توانی از ۲ هست که میشه به دلخواه این فرض رو کرد ولی زیاد هم مهم نیست چون به هر حال از مرتبه‌ی n هست حاصل جمع فوق).
خلاصه در هر بار اجرای حلقه‌ی بیرونی، به تعداد ۲n-1 تا دستور اجرا میشه. دقت شود که حلقه‌ی وسطی مستقل از متغیر کنترلی حلقه‌ی اول یعنی i هست. حلقه‌ی بیرونی هم که [tex]\log(n)[/tex] بار اجرا میشه پس در نهایت میشه [tex]\log(n)\times n[/tex]

پی‌نوشت: علت اینکه مرتبه‌شون نمیشه گفت m*n این هست که متغیرهاشون به هم وابسته هستو یعنی حلقه‌ی سوم تا j میره هر بار

سلام
درسته که حلقه for اول متغیرش i هست و وابستگی نداره با حلقه های داخلیش اما در هر صورت این ۳ حلقه تو در تو هستن هر سه تاشون
اولی که متغیر i هست مرتبش log n هست
و دومین حلقه با متغیر j هم مرتبش log n هست و تا اینجا میشه log n * log n
و حلقه داخلی سوم هم که مرتبش n هست پس دستور ++x باید به مقدار Log n * Log n * n بار تکرار بشه !! که میشه گزینه ۴!!
قاعدتا باید اینطور باشه چون حلقه اول مجزا نیست و ۳ حلقه تودرتو هستن

میشه لطفا بیشتر توضیح بدین
اینکه اولی i هست و مرتبه‌ش log n درسته. حلقه‌ی دوم هم همینطور. اما چرا می‌گید حلقه‌ی آخر از مرتبه‌ی n هست؟ حلقه‌ی آخر فقط یک بار به تعداد n دفعه دستور ++x رو اجرا می‌کنه (اونم وقتی که j=n) میشه. در بقیه‌ی موارد به تعداد n/2 و n/4 و ... ۱ بار دستور ++x رو اجرا می‌کنه. من نمی‌دونم کتابای کنکوری چه میانبرهایی ارائه دادند ولی بله اگر حلقه‌ی سوم مستقل از حلقه‌ی دوم بود اون موقع می‌شد ضرب کرد ولی الان حلقه‌ی دوم و سوم رو باید با هم در نظر بگیرید. دستور ++x هر بار k تا اجرا میشه که k توسط حلقه‌ی دوم تعیین می‌شه و مقدارش ۱ و ۲ و ۴ و ۸ و ... و n هست که میشه حدود ۲n. یعنی دو حلقه روی هم ۲n بار دستور ++x رو اجرا می‌کنند.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

delete4all پاسخ داده:

RE: مرتبه ی زمانی - IT88

دوستان کسی نظری نداشت دیگه

راهنمایی کنید مجدد لطفا
نقل قول این ارسال در یک پاسخ

ارسال:
  

hamsargol پاسخ داده:

RE: مرتبه ی زمانی - IT88

(۰۳ مهر ۱۳۹۵ ۰۹:۰۰ ق.ظ)delete4all نوشته شده توسط:  دوستان کسی نظری نداشت دیگه

راهنمایی کنید مجدد لطفا

سلام حلقه اول که واضحه. اینو بزار کنار
برای یک n توان ۲ روی کاغذ حلقه۲و۳ رو انجام بده از مرتبه ۲n میشه
حلقه ۲و۳ تو هم ضرب نمیشن چون متغیر وابسته دارن!!
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

delete4all پاسخ داده:

RE: مرتبه ی زمانی - IT88

behnam جان ممنون Heart
hamsargol ممنون Heart
بخاطر راهنمایهای خوبتون
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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