درود
مقسمی جواب رو گزینه ۳ اعلام کرده و توضیحی نداده.
چطور میشه اینکار رو در log n انجام داد؟
لطفا راهنمایی کنید
(۲۸ دى ۱۳۹۲ ۱۰:۰۸ ق.ظ)tayebe68 نوشته شده توسط: درود
مقسمی جواب رو گزینه ۳ اعلام کرده و توضیحی نداده.
چطور میشه اینکار رو در log n انجام داد؟
لطفا راهنمایی کنید
سلام دوست عزیز
سوال رو بدقت مطالعه کنید!!
آرایه کاملا مرتب هست ، پس میشه فهمید اعداد منفی ابتدا (کوچکترین ها) تا انتهای آرایه(بزرگترین) عدد قرار گرفته. روش حل معلومه، وسط آرایه رو در نظر میگیریم اگر اندیس آرایه با مقدار خانه برابر بود جوابه اگر کوچیکتر بود عملیاتو روی قسمت چپ آرایه و اگر بزرگتر بود عملیات رو به صورت بازگشتی روی قسمت راست آرایه تکرار میکنیم، خوب این در واقع همون جستجوی دودویی هست دیگه، که پیچیدگی زمانی برابر LOGn داره
(۲۸ دى ۱۳۹۲ ۰۶:۴۴ ب.ظ)Mindhunter نوشته شده توسط:(28 دى ۱۳۹۲ ۱۰:۰۸ ق.ظ)tayebe68 نوشته شده توسط: درود
مقسمی جواب رو گزینه ۳ اعلام کرده و توضیحی نداده.
چطور میشه اینکار رو در log n انجام داد؟
لطفا راهنمایی کنید
سلام دوست عزیز
سوال رو بدقت مطالعه کنید!!
آرایه کاملا مرتب هست ، پس میشه فهمید اعداد منفی ابتدا (کوچکترین ها) تا انتهای آرایه(بزرگترین) عدد قرار گرفته. روش حل معلومه، وسط آرایه رو در نظر میگیریم اگر اندیس آرایه با مقدار خانه برابر بود جوابه اگر کوچیکتر بود عملیاتو روی قسمت چپ آرایه و اگر بزرگتر بود عملیات رو به صورت بازگشتی روی قسمت راست آرایه تکرار میکنیم، خوب این در واقع همون جستجوی دودویی هست دیگه، که پیچیدگی زمانی برابر LOGn داره
اما دلیل نمیشه که چون کوچکتر بود، قسمت چپ رو بررسی کنیم. شاید عنصر با اندیس برابر توی قسمت راست باشه
بهتر بود اینطور میگفتید. که میانه رو بررسی میکنیم. اگه عدد میانه از اندیسش کوچکتر بود، قسمت راست رو بررسی میکنیم. چون میدونیم اعداد مرتب هستند و اعدادی که سمت چپ قرار میگیرند همشون از اندیسشون کوچکترن. اما سمت راست، مساوی یا برابرند.
اگر هم عدد از اندیسش بزرگتر بود، با همین روال، قسمت سمت چپ رو بررسی میکنیم
(۲۸ دى ۱۳۹۲ ۰۶:۵۱ ب.ظ)hoomanab نوشته شده توسط:(28 دى ۱۳۹۲ ۰۶:۴۴ ب.ظ)Mindhunter نوشته شده توسط:(28 دى ۱۳۹۲ ۱۰:۰۸ ق.ظ)tayebe68 نوشته شده توسط: درود
مقسمی جواب رو گزینه ۳ اعلام کرده و توضیحی نداده.
چطور میشه اینکار رو در log n انجام داد؟
لطفا راهنمایی کنید
سلام دوست عزیز
سوال رو بدقت مطالعه کنید!!
آرایه کاملا مرتب هست ، پس میشه فهمید اعداد منفی ابتدا (کوچکترین ها) تا انتهای آرایه(بزرگترین) عدد قرار گرفته. روش حل معلومه، وسط آرایه رو در نظر میگیریم اگر اندیس آرایه با مقدار خانه برابر بود جوابه اگر کوچیکتر بود عملیاتو روی قسمت چپ آرایه و اگر بزرگتر بود عملیات رو به صورت بازگشتی روی قسمت راست آرایه تکرار میکنیم، خوب این در واقع همون جستجوی دودویی هست دیگه، که پیچیدگی زمانی برابر LOGn داره
اما دلیل نمیشه که چون کوچکتر بود، قسمت چپ رو بررسی کنیم. شاید عنصر با اندیس برابر توی قسمت راست باشه
بهتر بود اینطور میگفتید. که میانه رو بررسی میکنیم. اگه عدد میانه از اندیسش کوچکتر بود، قسمت راست رو بررسی میکنیم. چون میدونیم اعداد مرتب هستند و اعدادی که سمت چپ قرار میگیرند همشون از اندیسشون کوچکترن. اما سمت راست، مساوی یا برابرند.
اگر هم عدد از اندیسش بزرگتر بود، با همین روال، قسمت سمت چپ رو بررسی میکنیم
خوب آخه تو این آرایه میانه عنصر وسط میشه دیگه، نمیشه؟؟؟
بله. مثلا فرض کنید عنصر وسط اندیسش ۴ باشه و عدد درونش ۲ باشه. چون آرایه مرتبه، میدونیم که اعداد قبل از اون، ازش کوچکترن. پس هیچ کدوم با اندیسشون برابر نیستند.
Sent from my SM-T210R using Tapatalk
(۲۸ دى ۱۳۹۲ ۰۷:۰۴ ب.ظ)Mindhunter نوشته شده توسط:چون آرایه مرتب است میانه را در زمان تتای یک بدست میآوریم.دو اتقاق ممکن است بیفتد۱_اندیس از محتوا کوچکتر است پس از آنجاییکه آرایه مرتب و عناصر هم مجزا هستند پس عناصر بعد از میانه هم همین ویژگی رو دارند در نتبجه عناصر بعدی را در نظر نمیگیریم ۲_اندیس از محتوا بزرگتر است پس عناصر قبلی هم همین ویژگی رو دارند پس آنها رو در نظر نمیگیریم یعنی همیشه ۵۰درصد عناصر دور ریخته میشوند پس کافی است محتوی میانه رو با اندیس آن چک کنیم که باتتای یک می شود این کار را انجام داد و چون آرایه مرتب است ۵۰ درصد عناصر را حذف میکنیم و همین روند را تکرار میکنیم. . که رابطه بازگشتی اون میشود مثل رابطه جستجوی دودویی که با استفاده از قضیه اساسی میشود logn.ین راه حل کامل دکتر سید جوادی هستش توی جزوه(28 دى ۱۳۹۲ ۰۶:۵۱ ب.ظ)hoomanab نوشته شده توسط:(28 دى ۱۳۹۲ ۰۶:۴۴ ب.ظ)Mindhunter نوشته شده توسط:(28 دى ۱۳۹۲ ۱۰:۰۸ ق.ظ)tayebe68 نوشته شده توسط: درود
مقسمی جواب رو گزینه ۳ اعلام کرده و توضیحی نداده.
چطور میشه اینکار رو در log n انجام داد؟
لطفا راهنمایی کنید
سلام دوست عزیز
سوال رو بدقت مطالعه کنید!!
آرایه کاملا مرتب هست ، پس میشه فهمید اعداد منفی ابتدا (کوچکترین ها) تا انتهای آرایه(بزرگترین) عدد قرار گرفته. روش حل معلومه، وسط آرایه رو در نظر میگیریم اگر اندیس آرایه با مقدار خانه برابر بود جوابه اگر کوچیکتر بود عملیاتو روی قسمت چپ آرایه و اگر بزرگتر بود عملیات رو به صورت بازگشتی روی قسمت راست آرایه تکرار میکنیم، خوب این در واقع همون جستجوی دودویی هست دیگه، که پیچیدگی زمانی برابر LOGn داره
اما دلیل نمیشه که چون کوچکتر بود، قسمت چپ رو بررسی کنیم. شاید عنصر با اندیس برابر توی قسمت راست باشه
بهتر بود اینطور میگفتید. که میانه رو بررسی میکنیم. اگه عدد میانه از اندیسش کوچکتر بود، قسمت راست رو بررسی میکنیم. چون میدونیم اعداد مرتب هستند و اعدادی که سمت چپ قرار میگیرند همشون از اندیسشون کوچکترن. اما سمت راست، مساوی یا برابرند.
اگر هم عدد از اندیسش بزرگتر بود، با همین روال، قسمت سمت چپ رو بررسی میکنیم
خوب آخه تو این آرایه میانه عنصر وسط میشه دیگه، نمیشه؟؟؟
(۲۸ دى ۱۳۹۲ ۰۹:۱۴ ب.ظ)hnarghani نوشته شده توسط: چون آرایه مرتب است میانه را در زمان تتای یک بدست میآوریم.دو اتقاق ممکن است بیفتد۱_اندیس از محتوا کوچکتر است پس از آنجاییکه آرایه مرتب و عناصر هم مجزا هستند پس عناصر بعد از میانه هم همین ویژگی رو دارند در نتبجه عناصر بعدی را در نظر نمیگیریم ۲_اندیس از محتوا بزرگتر است پس عناصر قبلی هم همین ویژگی رو دارند پس آنها رو در نظر نمیگیریم یعنی همیشه ۵۰درصد عناصر دور ریخته میشوند پس کافی است محتوی میانه رو با اندیس آن چک کنیم که باتتای یک می شود این کار را انجام داد و چون آرایه مرتب است ۵۰ درصد عناصر را حذف میکنیم و همین روند را تکرار میکنیم. . که رابطه بازگشتی اون میشود مثل رابطه جستجوی دودویی که با استفاده از قضیه اساسی میشود logn.ین راه حل کامل دکتر سید جوادی هستش توی جزوه
کاملا متوجه شدم ، سپاس