(۱۹ اسفند ۱۳۹۰ ۰۵:۳۵ ب.ظ)mfXpert نوشته شده توسط:  این تکه کدی که قرار دادید مشکل داره.در واقع ممکنه حلقه for بینهایت بار اجرا بشه ( چون n داره هر دفعه افزایش پیدا می کنه)
اگر به جای n++ قرار بدیم i++ اون وقت مرتبه قطعه کد میشه بیگ اوی n

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

(۱۹ اسفند ۱۳۹۰ ۰۳:۴۸ ب.ظ)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 و امگا و تتا بیان میشه
یعنی باید تعداد مراحل یا قدم ها رو حساب کنیم و در قالب سه تابع فوق اون رو بیان کنیم

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

CodeCogsEqn.gif
اندازه فایل: ۴۰۹ bytes

CodeCogsEqn.gif
اندازه فایل: ۴۰۹ bytes

(۱۹ اسفند ۱۳۹۰ ۰۴:۳۶ ب.ظ)farzaneh6 نوشته شده توسط:  تعداد گام رو چطوری باید محاسبه کرد ؟

تکرار ما وابسته به ارزش k هست.پس باید مقدار k را دنبال کنیم.
۱) k=n
۲) k=n/2
۳) k=n/4
.
.
.
m)
تو این مرحله k=n/2^m-1
که مقدار k=<1 هست

میشه برای این سوال تعداد گام ها رو بگید ، من متوجه نشدم

بلی درسته
باید بر حسب n بنویسم چند بار تکرار میشه ، ولی بلد نیستم