سلام دوستان ، کسی می دونه برای حلقه while مرتبه زمانی چطوری میشه ؟الان برای این سوال برای حلقه for میشه n+1 ، برای while چی میشه ؟؟
(۱۹ اسفند ۱۳۹۰ ۰۳:۴۸ ب.ظ)farzaneh6 نوشته شده توسط: سلام دوستان ، کسی می دونه برای حلقه while مرتبه زمانی چطوری میشه ؟الان برای این سوال برای حلقه for میشه n+1 ، برای while چی میشه ؟؟
سلام.
while هیچ فرق با for نداره.یعنی همون طور کهتعداد تکرار های for و حساب میکردی while هم همینطوری حساب میشه.
اینجا مقدار k تا وقتی بزرگتر از یک باشه میره جلو.و هر دفه تقسیم بر ۲ میشه پس به تعداد log n بار تکرار میشه.
تعداد گام رو چطوری باید محاسبه کرد ؟
(۱۹ اسفند ۱۳۹۰ ۰۴:۰۵ ب.ظ)wildcoder نوشته شده توسط:(19 اسفند ۱۳۹۰ ۰۳:۴۸ ب.ظ)farzaneh6 نوشته شده توسط: سلام دوستان ، کسی می دونه برای حلقه while مرتبه زمانی چطوری میشه ؟الان برای این سوال برای حلقه for میشه n+1 ، برای while چی میشه ؟؟
سلام.
while هیچ فرق با for نداره.یعنی همون طور کهتعداد تکرار های for و حساب میکردی while هم همینطوری حساب میشه.
اینجا مقدار k تا وقتی بزرگتر از یک باشه میره جلو.و هر دفه تقسیم بر ۲ میشه پس به تعداد log n بار تکرار میشه.
منظور از مرتبه زمانی همون مرتبه اجرایی برنامه است که بر حسب توابع O و امگا و تتا بیان میشه
یعنی باید تعداد مراحل یا قدم ها رو حساب کنیم و در قالب سه تابع فوق اون رو بیان کنیم
چطوری میشه بر حسب توابع نوشت ؟
[attachment=3222][attachment=3222]
(19 اسفند ۱۳۹۰ ۰۴:۳۶ ب.ظ)farzaneh6 نوشته شده توسط: تعداد گام رو چطوری باید محاسبه کرد ؟
تکرار ما وابسته به ارزش k هست.پس باید مقدار k را دنبال کنیم.
۱) k=n
۲) k=n/2
۳) k=n/4
.
.
.
m)
تو این مرحله k=n/2^m-1
که مقدار k=<1 هست
این تکه کدی که قرار دادید مشکل داره.در واقع ممکنه حلقه for بینهایت بار اجرا بشه ( چون n داره هر دفعه افزایش پیدا می کنه)
اگر به جای n++ قرار بدیم i++ اون وقت مرتبه قطعه کد میشه بیگ اوی n
میشه برای این سوال تعداد گام ها رو بگید ، من متوجه نشدم
بلی درسته
باید بر حسب n بنویسم چند بار تکرار میشه ، ولی بلد نیستم
(۱۹ اسفند ۱۳۹۰ ۰۵:۳۵ ب.ظ)mfXpert نوشته شده توسط: این تکه کدی که قرار دادید مشکل داره.در واقع ممکنه حلقه for بینهایت بار اجرا بشه ( چون n داره هر دفعه افزایش پیدا می کنه)
اگر به جای n++ قرار بدیم i++ اون وقت مرتبه قطعه کد میشه بیگ اوی n
چرا میشه [tex]O(n)[/tex]
؟؟
نمیشه n logn ؟