با عرض سلام و خسته نباشیید
من یه سوال داشتم میخواستم اگه امکانش هست ابتدا یک توضیحی در مورد اینکه باید چطوری مرتبه ی زمانی یک تک کد رو به دست بیاریم بدهید و بعدم مرحله به مرحله و توضیح فاری و تشریحی کامل توضیح بدهید چوری این مرتبه ی زمانی این تک کدها ها رو به دست آوریم , و در اخر هم اگه راه حل کوتاه تری یا تستی سراغ دارید بفرمایید باتشکر
کدها در پیوست قرار دارند.
راه حل خاصی نداره، باید تحلیل کنین ببینین واقعاً حلقه‌هاتون چند بار اجرا میشن!
مثلاً در مورد دومی، برای همون دور اول اجرای حلقه‌ی بیرونی (یعنی برای i=1) به دلیل صفر شدن n در حلقه‌ی داخلی دیگه حلقه بیرونی اجرا نمیشه. به عبارت دیگه حلقه‌ی بیرونی تنها یک بار اجرا میشه کلاً. در حلقه داخلی هم با هر بار افزایش j مقدار n کاهش پیدا می‌کنه و تا زمانی که مقدار هر دوتاشون برابر بشه (در نقطه‌ی n0/2)، در نتیجه این حلقه هم n/2 بار اجرا میشه. پس کل دفعات اجرای x = x + 1 برابره با n/2 در در نتیجه مرتبه‌ی تکه کد دوم میشه [tex]\Theta(n)[/tex].
در مورد تکه کد اولی هم تعداد دفعات اجرای حلقه‌ی بیرونی با همون استدلال n/2 هستش. بنابراین با n ارتباط خطی داره. تعداد دفعات اجرای حلقه داخلی هم با کم شدن n هر بار کم میشه، ولی همیشه بین n (در ابتدا) و n/2 (در پایان) قرار داره، بنابراین این هم ارتباط خطی با n داره. پس کل دفعات اجرای x = x + 1 برابر با ضریبی از [tex]n^{2}[/tex] میشه و در نتیجه مرتبه‌ی کل کد [tex]\Theta(n^{2})[/tex] هستش.
در مورد تعداد دفعات اجرای x = x+1 (و در نتیجه مرتبه‌کل کد) در کد سوم، اینطوری بررسی می‌کنیم که برای i = 1 حلقه‌ی داخلی (و در نتیجه کد x = x+1) به تعداد n بار اجرا میشه. برای i = 2 حلقه‌ی داخلی n/2 بار اجرا میشه. برای i = 3 حلقه‌ی داخلی n/3 بار اجرا میشه و... .
بنابراین کل دفعات اجرای کد x = x + 1 (و مرتبه‌ی کد سوم) برابره با:
[tex]n \frac{n}{2} \frac{n}{3} \frac{n}{4} ...=n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)=\Theta(n\cdot log(n))[/tex]