درود و سپاس
سوال مربوط به مرتبه زمانی ای تی ۸۸ هستش . من میدونم مرتبه زمانی خط اول میشه log n بخاطر i * 2 ولی چرا دو خط بعدی که دو حلقه تو در تو هستند بخاطر j , چرا مرتبه زمانی شون میشه n که در نهایت پاسخش بشه گزینه ۳؟ مگه حلقه های تو در تو مرتبه زمانی شون نمیشه mn ؟
[attachment=20614]
(۳۰ شهریور ۱۳۹۵ ۰۶:۵۳ ب.ظ)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 میره هر بار
نقل قول: دو حلقهی داخلی مستقل از حلقهی بیرونی هستند و راحتتر میشه حساب کرد که دستور [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 بار تکرار بشه !! که میشه گزینه ۴!!
قاعدتا باید اینطور باشه چون حلقه اول مجزا نیست و ۳ حلقه تودرتو هستن
میشه لطفا بیشتر توضیح بدین
دوستان کسی نظری نداشت دیگه
راهنمایی کنید مجدد لطفا
(۳۱ شهریور ۱۳۹۵ ۰۹:۴۴ ق.ظ)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 بار تکرار بشه !! که میشه گزینه ۴!!
قاعدتا باید اینطور باشه چون حلقه اول مجزا نیست و ۳ حلقه تودرتو هستن
میشه لطفا بیشتر توضیح بدین
(۰۳ مهر ۱۳۹۵ ۰۹:۰۰ ق.ظ)delete4all نوشته شده توسط: دوستان کسی نظری نداشت دیگه
راهنمایی کنید مجدد لطفا
سلام حلقه اول که واضحه. اینو بزار کنار
برای یک n توان ۲ روی کاغذ حلقه۲و۳ رو انجام بده از مرتبه ۲n میشه
حلقه ۲و۳ تو هم ضرب نمیشن چون متغیر وابسته دارن!!
behnam جان ممنون
hamsargol ممنون
بخاطر راهنمایهای خوبتون