تالار گفتمان مانشت

سلام دوستان ، کسی می دونه برای حلقه while مرتبه زمانی چطوری میشه ؟الان برای این سوال برای حلقه for میشه n+1 ، برای while چی میشه ؟؟

(19 اسفند 1390 03:48 ب.ظ)farzaneh6 نوشته شده توسط: [ -> ]سلام دوستان ، کسی می دونه برای حلقه while مرتبه زمانی چطوری میشه ؟الان برای این سوال برای حلقه for میشه n+1 ، برای while چی میشه ؟؟

سلام.
while هیچ فرق با for نداره.یعنی همون طور کهتعداد تکرار های for و حساب میکردی while هم همینطوری حساب میشه.
اینجا مقدار k تا وقتی بزرگتر از یک باشه میره جلو.و هر دفه تقسیم بر 2 میشه پس به تعداد log n بار تکرار میشه.

تعداد گام رو چطوری باید محاسبه کرد ؟

---

(19 اسفند 1390 04:05 ب.ظ)wildcoder نوشته شده توسط: [ -> ]

(19 اسفند 1390 03:48 ب.ظ)farzaneh6 نوشته شده توسط: [ -> ]سلام دوستان ، کسی می دونه برای حلقه while مرتبه زمانی چطوری میشه ؟الان برای این سوال برای حلقه for میشه n+1 ، برای while چی میشه ؟؟

سلام.
while هیچ فرق با for نداره.یعنی همون طور کهتعداد تکرار های for و حساب میکردی while هم همینطوری حساب میشه.
اینجا مقدار k تا وقتی بزرگتر از یک باشه میره جلو.و هر دفه تقسیم بر ۲ میشه پس به تعداد log n بار تکرار میشه.

منظور از مرتبه زمانی همون مرتبه اجرایی برنامه است که بر حسب توابع O و امگا و تتا بیان میشه
یعنی باید تعداد مراحل یا قدم ها رو حساب کنیم و در قالب سه تابع فوق اون رو بیان کنیم

چطوری میشه بر حسب توابع نوشت ؟

[attachment=3222][attachment=3222]

(19 اسفند 1390 04:36 ب.ظ)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 بنویسم چند بار تکرار میشه ، ولی بلد نیستم

(19 اسفند 1390 05:35 ب.ظ)mfXpert نوشته شده توسط: [ -> ]این تکه کدی که قرار دادید مشکل داره.در واقع ممکنه حلقه for بینهایت بار اجرا بشه ( چون n داره هر دفعه افزایش پیدا می کنه)
اگر به جای n++ قرار بدیم i++ اون وقت مرتبه قطعه کد میشه بیگ اوی n

چرا میشه [tex]O(n)[/tex]
؟؟
نمیشه n logn ؟