نقل قول: دو حلقه‌ی داخلی مستقل از حلقه‌ی بیرونی هستند و راحت‌تر میشه حساب کرد که دستور [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 نوشته شده توسط:  

نقل قول: دو حلقه‌ی داخلی مستقل از حلقه‌ی بیرونی هستند و راحت‌تر میشه حساب کرد که دستور [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 نوشته شده توسط:  دوستان کسی نظری نداشت دیگه

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