تالار گفتمان مانشت
مرتبه زمانی - آی تی ۸۶ - نسخه‌ی قابل چاپ

مرتبه زمانی - آی تی ۸۶ - Ametrine - 24 مهر ۱۳۹۳ ۱۰:۴۲ ب.ظ

این سوال و مشابهش که تو کنکور ۸۴ اومده، فقط از راه مقدار دادن و تریس کردن حل میشه؟
راه حل سریع تری نداره؟
با همین روش مقدار دادن هم لطفاً حلش کنید.

[attachment=17007]

RE: مرتبه زمانی - آی تی ۸۶ - MiladCr7 - 24 مهر ۱۳۹۳ ۱۱:۳۴ ب.ظ

(۲۴ مهر ۱۳۹۳ ۱۰:۴۲ ب.ظ)Ametrine نوشته شده توسط:  این سوال و مشابهش که تو کنکور ۸۴ اومده، فقط از راه مقدار دادن و تریس کردن حل میشه؟
راه حل سریع تری نداره؟
با همین روش مقدار دادن هم لطفاً حلش کنید.

سلام.اگه دقت کنی میبینی توی حلقه دوم هربار از n هم داره یه واحد کم میشه.پس واضحه که برای I=1 توی حلقه دوم جمله اصلی به اندازه n/2 تکرار میشه ( به این علت که هر بار jداره اضافه میشه و n همداره کم میشه پس تا وقتی که j به n/2 برسه اجرا میشه ) و الان مقدار n به n/2 کاهش پیدا کرده ( به خاطر اینکه هر بار یه واحد ازش کم کردیم ) و به ازای I=2 حلقه دوم دوباره به اندازه n/2اجرا میشه و چون الان مقدار n هم n/2 هست پس تقسیمش به ۲ مقدار n/4 رو میده و به ازای n=3 هم نصف مقدار فعلی n که n/4 هست اجرا میشه یعنی n/8 و به همین صورت ادامه پیدا میکنه
که یه سری هندسی هستش که از حلش تتای n به دست میاد
امیدوارم متوجه شده باشید

RE: مرتبه زمانی - آی تی ۸۶ - MiladCr7 - 25 مهر ۱۳۹۳ ۱۱:۳۹ ق.ظ

(۲۵ مهر ۱۳۹۳ ۱۰:۴۸ ق.ظ)Aurora نوشته شده توسط:  
(24 مهر ۱۳۹۳ ۱۰:۴۲ ب.ظ)Ametrine نوشته شده توسط:  این سوال و مشابهش که تو کنکور ۸۴ اومده، فقط از راه مقدار دادن و تریس کردن حل میشه؟
راه حل سریع تری نداره؟
با همین روش مقدار دادن هم لطفاً حلش کنید.
یک سوال
حلقه دوم از i=1 شروع میشه یا j=1 ؟

از j=1 شروع میشه