انجمنصفحه اولجستجوی انجمن

[Masoud05]

[mamat]

گزینه ۱ صحیح است
شاید برای n های کوچک گزینه ۳ مناسبتر باشد اما با در نظر گرفتن n های بزرگ گزینه ۱ صحیح است

[Masoud05]

(۰۲ مهر ۱۳۹۰ ۱۲:۱۲ ق.ظ)mamat نوشته شده توسط:  گزینه ۱ صحیح است
شاید برای n های کوچک گزینه ۲ مناسبتر باشد اما با در نظر گرفتن n های بزرگ گزینه ۱ صحیح است

در تحلیل زمانی نباید برای n های کوچک مسئله رو حل کرد( چون احتمال خطا داره )مگر سوالاتی مثل اینکه فلان خط در شبه کد چندبار اجرا میشود که اون مقدار دقیق رو غالبا از ما می پرسن (و یا مقدار فلان متغیر چیه --> واضح هست که برای هر nی چه کوچک و چه بزرگ جواب شما یکی هست )اما توی این سوال ممکنه شما رو گمراه کنه .

البته گزینه ۱ صحیح هست( خیلیا گزینه ۳ رو زدن ).

[mamat]

(۰۲ مهر ۱۳۹۰ ۱۲:۲۱ ق.ظ)Masoud05 نوشته شده توسط:  در تحلیل زمانی نباید برای n های کوچک مسئله رو حل کرد( چون احتمال خطا داره )مگر سوالاتی مثل اینکه فلان خط در شبه کد چندبار اجرا میشود که اون مقدار دقیق رو غالبا از ما می پرسن (و یا مقدار فلان متغیر چیه --> واضح هست که برای هر nی چه کوچک و چه بزرگ جواب شما یکی هست )اما توی این سوال ممکنه شما رو گمراه کنه .

این رو میدونم و از صورت سوال هم مشخصه فقط خواستم نتیجه ای که برای مقادیر کوچک n بدست میاد رو هم گفته باشم و برای کسانی که بیشتر با مقدار دهی این نوع سوالهارو حل میکنن مشخص بشه این سوال تا تقریبا مقدار n=20 میتونه گزینه ۳ صحیح باشه
ببخشین تو پست قبلی من اشتباها ۲ نوشتم که تصحیح میکنم

(۰۲ مهر ۱۳۹۰ ۱۲:۱۲ ق.ظ)mamat نوشته شده توسط:  شاید برای n های کوچک گزینه ۲ مناسبتر باشد

در ضمن داداش مسعود یکمی مارو دریاب ما دیگه مثل شما تو ساختمان و الگوریتم استخون نشکوندیم اینارو هم که میتونیم جواب بدیم تو ته ذهنمون یه چیزایی از قدیما مونده بود همین!!!
البته پیش شما دیگه این جسارتو نمیکنیم رو حرفتون حرف بزنیم

[admin]

زمانی که دکتر قدسی ایران بودن در مورد این سوال خیلی دعواها ایجاد شده بود، گزینه درست همون گزینه ۱ هست. درسته چند تا دونه log n هست اما تو مجموع که میشه k logn+n تاثیری نداره.

[fatima1537]

گزینه ۱-چون تعداد زوجها=n/2 و فردها هم = n/2 است
و زوجها هم پس از نصف شدن میشوند ۲ دسته که تعداد هردسته n/4 هست وچون زوجها پس از نصف شدن به فرد تبدیل میشوند و دیگر این الگوریتم ادامه پیدا نمیکند یک تابع خطی داریم:
n/2)+(n/4)+(n/4)=
n/2+n/2=
n

[mamat]

(۰۲ مهر ۱۳۹۰ ۰۲:۱۱ ب.ظ)fatima1537 نوشته شده توسط:  وچون زوجها پس از نصف شدن به فرد تبدیل میشوند و دیگر این الگوریتم ادامه پیدا نمیکند

البته اینو بگم که چرا باز این الگوریتم برای نصف زوجها ادامه پدا میکنه و همینطور ادامه خواهد داشت
چون همه زوجها بعد نصف شدن به فرد تبدیل نمیشوند
برای مثال ۱۶ رو فرض کنید
تابع زمانی این الگوریتم به صورت زیر است
$T(n)=2\frac{n}{2^{1}} 2\frac{n}{2^{2}} \frac{n}{2^{3}} ...$
که میشه اینطوری هم نوشت
$T(n)=\sum_{i=1}^{\left \lceil \log_{2}n \right \rceil}\frac{n}{2^{i}}$

[fatima1537]

(۰۲ مهر ۱۳۹۰ ۰۲:۳۳ ب.ظ)mamat نوشته شده توسط:  البته اینو بگم که چرا باز این الگوریتم برای نصف زوجها ادامه پدا میکنه و همینطور ادامه خواهد داشت
چون همه زوجها بعد نصف شدن به فرد تبدیل نمیشوند
برای مثال ۱۶ رو فرض کنید

بله حرفتون درسته
چون تعدادشون کم بود‌، برای n های زیاد توی محاسبه تاثیری ندارند.شما به شکل قابل قبول تری اثبات کردید روش من ذهنی بود