سلام
جواب گزینه ۱ هست
کسی میتونه برام توضیح بده.یک دنیا ممنونش میشم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۷ آذر ۱۳۹۲ ۰۹:۰۴ ب.ظ)tarane1992 نوشته شده توسط: سلام
جواب گزینه ۱ هست
کسی میتونه برام توضیح بده.یک دنیا ممنونش میشم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
مرتبه زمانی برای هر مرحله:
۱) مرتبه یک
۲) پیدا کردن میانه یک لیست مرتب از مرتبه یک است.
۳) جستجوی دو دویی که از مرتبه log تعداد عناصر B هست = log m
۴) مرتبه یک
۵ و ۶) بین این دو مرحله فقط یکی انجام میشود. هر دو به علت بازگشتی بودن و نصف شدن تعداد n از مرتبه T (n/2 , m هست.
حالا برای مرتبه کل چون پشت سر هم انجام شدند باید اینها را با هم جمع کرد که گزینه ۱ میشه.
ممنونم از پاسخ شما.
سوالی دارم اینکه اون مراحلی که مرتبه ۱ هست یعنی با یک مقایسه میشه به جواب رسید ؟
آخه مگه عدد ثابت باشه اون وقت فقط نمیشه مرتبه یک ؟پس چرا اینجا شده مرتبه یک.
اینکه چرا گاهی اوقات بعضی سوال ها میانه رو n میگیرن؟(چون دقیقا وسط آرایه هست یعنی n/2 هست دیگه) اینجه چرا نشد n ؟
ممنون میشم پاسخ بدید.
موفق باشید.
(۳۰ آذر ۱۳۹۲ ۰۴:۳۳ ب.ظ)tarane1992 نوشته شده توسط: ممنونم از پاسخ شما.خواهش میکنم.
سوالی دارم اینکه اون مراحلی که مرتبه ۱ هست یعنی با یک مقایسه میشه به جواب رسید ؟
آخه مگه عدد ثابت باشه اون وقت فقط نمیشه مرتبه یک ؟پس چرا اینجا شده مرتبه یک.
اینکه چرا گاهی اوقات بعضی سوال ها میانه رو n میگیرن؟(چون دقیقا وسط آرایه هست یعنی n/2 هست دیگه) اینجه چرا نشد n ؟
ممنون میشم پاسخ بدید.
موفق باشید.
بله اگر عدد ثابت باشه میشه مرتبه یک، اینجا هم در مراحل ۱ و ۴ کاری که انجام میشه یک جایگذاری است یعنی مقداری را با عبارات ریاضی حساب میکنیم و در متغیر k و x جایگذاری میکنیم توجه داشته باشید تعداد اعمال مهم است نه مقدار متغیرهایی که با هاشون کار میکنیم.
به دست آوردن میانه دریک لیست نا مرتب از مرتبه n هست و در کل به دست آوردن k امین کوچکترین عنصر (میانه = ۲/n امین کوچکترین عنصر است ) از مرتبه n هست. ولی اگر لیست (یا همان آرایه مان) مرتب باشد مشخص است که میانه در وسط لیست هست پس با مرتبه یک پیدا میشه.
بله دقیقا حق با شماست.
فهمیدم ازتون سپاسگذارم.
موفق باشید.