بچه ها کسی می تونه بگه چرا مرتبه زمانی این الگوریتم n میشه
for i to n do
for j to n do
{
;x=x+1
;n=n-1
}
با سلام دوست عزیز ببیند به ازای i=1 حلقه دوم n/2 اجرا میشه چرا؟ چون که به ازای هر بار اجرای حلقه دوم که همون j هستش یک دونه هم از n کم میشه یعنی توی هر بار اجرا عملا شرط داره دوتا دوتا کم میشه چون مقدار j داره یکی زیاد میشه و مقدار n هم داره یکی کم میشه پس بازه ی اجرای حلقه دوم داره از دو طرف کم میشه یعنی هم داره j زیاد میشه و هم n داره کم میشه ولی حلقه ی اول فقط داره n کم میشه ازش
پس وقتی حلقه دوم دیگه شرطش نقض بشه مقدار n تقریبا نصف شده پس برای اجرای i=2 مقدار n نصف شده است خوب حالا به ازای i=2
حلقه دوم این بار داره باز هم نصف میکنه مقدار n پس n/2/2 = n/4 میشه دیگه و به همین ترتیب هر دقعه مقدار داره تقسیم بر ۲ میشه پس جمع دنباله اینطوری میشه
n/2+n/4+n/8+n/16+....
خوب اگر از یک n فاکتور بگیریم میشه چی؟
۱/۲+۱/۴+۱/۸+۱/۱۶+....
خوب این یک سری هندسی نامتناهی که قدر نسبت اون ۱/۲ هست پس طبق قضیه سری ها داریم مجموع این میشه جمله اول تقسیم بر ۱-قدر نسبت
جمله اول که یک دوم هست صورت میشه ۱/۲ و مخرج هم میشه ۱-۱/۲ که میشه ۱/۲
۱/۲ تقسیم بر ۱/۲ میشه ۱
۱*N=n پس حاصل سری میشه n که میشه مرتبه خطی پس از مرتبه تتا n هستش
(ببخشید اگر یکم ریاضیاتشو بد نوشتم کلا این پرانتز مخرج این چیزا رو تو انجمن نمیشه خوب نوشت
)امیدوارم متوجه شده باشید موفق باشید
یعنی موقعی که داره از n کم میشه این روی متغیر i تاثیر داره؟
من منظورتونو دقیقا از این سوال نفهمیدم ولی اگر منظورتون درست فهمیده باشم که منظورتون تاثیر n روی حلقه اول هست بله دیگه حلقه اول یعنی i تا کی اجرا میشه؟ تا وقتی که کوچکتر مساوی n باشه خوب متغیر n داره توی حلقه دوم هر بار که اجرا میشه یکی کم میشه یه بار فک کنم با یه عدد تریس کنید و توضیحاتی که دادمو بخونید متوجه شید کاملا
ببخشید فرض کنید به n=8 باشه در این صورت در حلقه دوم متغیر n تا عدد ۵ میره بعدش از حلقه خارج میشه سوال اصلی من اینه که آیا متغیر n که در حلقه اول هستش اونم برابر ۵ میشه یا نه؟ چرا متغیر n که در حلقه دوم هستش روی حلقه اول تاثیر داره؟
دوست عزیز ۸ فرض کنیم تا وقتی ۴ بشه اجرا میشه نه ۵ مقدار i کوچکتر مساوی n هست
بله تاثیر داره دیگه مشکل شما اینه برنامه نویسیتون ضعیفه کلا بچه های که برنامه نویسیشون ضعیفه بعضا سر این موضوعا قاطی می کنن
ببیند مقدار n توی یک جای ذخیره شده و هر دقعه که برنامه داره اجرا میشه این n خونده میشه از اون مکان n که مقدار ثابت نیست داره تغییر می کنه موفق باشید