۰
subtitle
ارسال: #۱
  
مرتبه ی زمانی - IT88
درود و سپاس
سوال مربوط به مرتبه زمانی ای تی ۸۸ هستش . من میدونم مرتبه زمانی خط اول میشه log n بخاطر i * 2 ولی چرا دو خط بعدی که دو حلقه تو در تو هستند بخاطر j , چرا مرتبه زمانی شون میشه n که در نهایت پاسخش بشه گزینه ۳؟ مگه حلقه های تو در تو مرتبه زمانی شون نمیشه mn ؟
سوال مربوط به مرتبه زمانی ای تی ۸۸ هستش . من میدونم مرتبه زمانی خط اول میشه log n بخاطر i * 2 ولی چرا دو خط بعدی که دو حلقه تو در تو هستند بخاطر j , چرا مرتبه زمانی شون میشه n که در نهایت پاسخش بشه گزینه ۳؟ مگه حلقه های تو در تو مرتبه زمانی شون نمیشه mn ؟
![](https://cdn.manesht.ir/20614___it88.png)
۳
ارسال: #۲
  
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 میره هر بار
ارسال: #۳
  
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 بار تکرار بشه !! که میشه گزینه ۴!!
قاعدتا باید اینطور باشه چون حلقه اول مجزا نیست و ۳ حلقه تودرتو هستن
میشه لطفا بیشتر توضیح بدین
ارسال: #۴
  
RE: مرتبه ی زمانی - IT88
(۳۱ شهریور ۱۳۹۵ ۰۹:۴۴ ق.ظ)delete4all نوشته شده توسط:اینکه اولی i هست و مرتبهش log n درسته. حلقهی دوم هم همینطور. اما چرا میگید حلقهی آخر از مرتبهی n هست؟ حلقهی آخر فقط یک بار به تعداد n دفعه دستور ++x رو اجرا میکنه (اونم وقتی که j=n) میشه. در بقیهی موارد به تعداد n/2 و n/4 و ... ۱ بار دستور ++x رو اجرا میکنه. من نمیدونم کتابای کنکوری چه میانبرهایی ارائه دادند ولی بله اگر حلقهی سوم مستقل از حلقهی دوم بود اون موقع میشد ضرب کرد ولی الان حلقهی دوم و سوم رو باید با هم در نظر بگیرید. دستور ++x هر بار k تا اجرا میشه که k توسط حلقهی دوم تعیین میشه و مقدارش ۱ و ۲ و ۴ و ۸ و ... و n هست که میشه حدود ۲n. یعنی دو حلقه روی هم ۲n بار دستور ++x رو اجرا میکنند.نقل قول: دو حلقهی داخلی مستقل از حلقهی بیرونی هستند و راحتتر میشه حساب کرد که دستور [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 بار تکرار بشه !! که میشه گزینه ۴!!
قاعدتا باید اینطور باشه چون حلقه اول مجزا نیست و ۳ حلقه تودرتو هستن
میشه لطفا بیشتر توضیح بدین
۰
ارسال: #۶
  
RE: مرتبه ی زمانی - IT88
ارسال: #۷
  
RE: مرتبه ی زمانی - IT88
behnam جان ممنون ![Heart Heart](images/smilies/heart.gif)
hamsargol ممنون![Heart Heart](images/smilies/heart.gif)
بخاطر راهنمایهای خوبتون
![Heart Heart](images/smilies/heart.gif)
hamsargol ممنون
![Heart Heart](images/smilies/heart.gif)
بخاطر راهنمایهای خوبتون
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
![]() |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۴,۶۱۰ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۳۰۵ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۲۶۵ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۲,۴۲۶ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۰,۹۷۹ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت | اsepid8994 | ۰ | ۱,۷۳۳ |
۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994 |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۶۹۸ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
مرتبه مانی | Sanazzz | ۳ | ۳,۵۸۷ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
![]() |
یافتن دو عدد پیچیدگی زمانی O(n) | porseshgar | ۲ | ۳,۸۲۸ |
۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ آخرین ارسال: porseshgar |
مرتبه زمانی | Sanazzz | ۰ | ۱,۹۷۸ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close