(۱۸ بهمن ۱۳۹۳ ۱۱:۰۴ ب.ظ)hamedmohsenee نوشته شده توسط:توضیحات کامل و درست(18 بهمن ۱۳۹۳ ۰۹:۱۹ ب.ظ)khordad.girl نوشته شده توسط: دوستان تو یه آرایه مرتب باید عدد اولی رو ببینیم با log n دنبال مکملش بگردیم ایا ؟ سوال ۴۱
نه به این شکل عمل می کنیم که دو تا اشاره گر یکی به اول ارایه و دیگری به اخر ارایه می زاریم جمع عدد اول وآخر رو با C مقایسه می کنیم اگر مساوی بود که حله گر کمتر از Cشد باید اشاره گر اول رو یکی جلو بیاریم اگر بیشتر از C شد باید اشاره گر اخر رویکی عقب بکشیم ودوباره تکرار کنیم خب مسلمه بدترینش زمانی رخ میده که کلا وجود نداشته باشه و اشاره گر ها یکیش بی تغییر باشه و اون یکی تا رسیدن به اشاره گر دیگه حرکت کنه و از مترتبه تعداد عناصر میشه
مرتبه n میشه
خب اشکال روش من چیه؟
(۱۸ بهمن ۱۳۹۳ ۱۱:۴۳ ب.ظ)khordad.girl نوشته شده توسط:شما یک عدد رو چک کردید ، با الگوریتم شما در بدترین،حالت وقتی مجبوریم مکمل همه عناصر رو چک کنیم میشه nlogn(18 بهمن ۱۳۹۳ ۱۱:۱۱ ب.ظ)Densike نوشته شده توسط:خب اشکال روش من چیه؟
(۱۸ بهمن ۱۳۹۳ ۱۱:۴۴ ب.ظ)Densike نوشته شده توسط:(18 بهمن ۱۳۹۳ ۱۱:۴۳ ب.ظ)khordad.girl نوشته شده توسط:شما یک عدد رو چک کردید ، با الگوریتم شما در بدترین،حالت وقتی مجبوریم مکمل همه عناصر رو چک کنیم میشه nlogn(18 بهمن ۱۳۹۳ ۱۱:۱۱ ب.ظ)Densike نوشته شده توسط:خب اشکال روش من چیه؟
درسته من بین این گزینه و n شک کردم که تو لحظه آخر زدم log n واقعا ناراحتم
(۱۸ بهمن ۱۳۹۳ ۱۱:۴۷ ب.ظ)khordad.girl نوشته شده توسط:دوست عزیز اصلا ناراحت نباش ... اسم این سوتی هست و همه سوتی دادیم ، شما تو این سوال ، من توی سوال دیگه(18 بهمن ۱۳۹۳ ۱۱:۴۴ ب.ظ)Densike نوشته شده توسط:(18 بهمن ۱۳۹۳ ۱۱:۴۳ ب.ظ)khordad.girl نوشته شده توسط:شما یک عدد رو چک کردید ، با الگوریتم شما در بدترین،حالت وقتی مجبوریم مکمل همه عناصر رو چک کنیم میشه nlogn(18 بهمن ۱۳۹۳ ۱۱:۱۱ ب.ظ)Densike نوشته شده توسط:خب اشکال روش من چیه؟
درسته من بین این گزینه و n شک کردم که تو لحظه آخر زدم log n واقعا ناراحتم
(۱۸ بهمن ۱۳۹۳ ۱۱:۴۸ ب.ظ)Densike نوشته شده توسط:(18 بهمن ۱۳۹۳ ۱۱:۴۷ ب.ظ)khordad.girl نوشته شده توسط:دوست عزیز اصلا ناراحت نباش ... اسم این سوتی هست و همه سوتی دادیم ، شما تو این سوال ، من توی سوال دیگه(18 بهمن ۱۳۹۳ ۱۱:۴۴ ب.ظ)Densike نوشته شده توسط:(18 بهمن ۱۳۹۳ ۱۱:۴۳ ب.ظ)khordad.girl نوشته شده توسط:شما یک عدد رو چک کردید ، با الگوریتم شما در بدترین،حالت وقتی مجبوریم مکمل همه عناصر رو چک کنیم میشه nlogn(18 بهمن ۱۳۹۳ ۱۱:۱۱ ب.ظ)Densike نوشته شده توسط:خب اشکال روش من چیه؟
درسته من بین این گزینه و n شک کردم که تو لحظه آخر زدم log n واقعا ناراحتم
دقیقا...
سلام دوستان، کلیدا اومده ؟؟
نه هنوز
راستی بچه ها درخت اییینه ایی هم مثال نقضش میشه مورب چپ با ۶گرهabcabc میشد هیچکدام
دوستایی که درخت قرمزو سیاهو ۰ زدید تحلیل کنید ببنیم چه جوریاس .
من که میگم با ۱۰۲۳ عنصر امکانش نیست حداقل ۰ تا داشته باشیم.
اره اگه یه عنصر بود طبق این خاصیتش که ریشه باس سیاه باشه میشد بگیم حداقل صفر تا ولی الان ....
بازم مطمین نیسم...... یکی تحلیل کنه لطفا
بزارین تحلیل ایدین نصیری شرق رو توی ۶۰۰ مساله ببینیم:
البته قبلش باید قانونای حاکم بر درخت قرمز سیاهو بدونی:
نصیری شرق برای ۱۲۸ نود نوشته:
درختی که تمام گره های آن سیاه است باید تمام مسیرهای از ریشه تا برگ آن هم طول بوده و درنتیجه کامل است.از سوی دیگر می دانیم تعداد گره های یک درخت کامل برابر ۲ به توان k منهای یک است و ۱۲۸=۲به توان ۷
(۱۹ بهمن ۱۳۹۳ ۰۲:۲۵ ب.ظ)hamedmohsenee نوشته شده توسط: بزارین تحلیل ایدین نصیری شرق رو توی ۶۰۰ مساله ببینیم:
البته قبلش باید قانونای حاکم بر درخت قرمز سیاهو بدونی:
نصیری شرق برای ۱۲۸ نود نوشته:
درختی که تمام گره های آن سیاه است باید تمام مسیرهای از ریشه تا برگ آن هم طول بوده و درنتیجه کامل است.از سوی دیگر می دانیم تعداد گره های یک درخت کامل برابر ۲ به توان k منهای یک است و ۱۲۸=۲به توان ۷
این الان یعنی چی؟؟؟؟جالبه چیزیو به چیز دیگری ربط دادین...من خودم حس میکنم ۱۰ نمیشه چون ۱۰ حداقل تعداد گره سیاهه اگر ۱۰۲۳ نود داشته باشیم با توجه به فرمول n=2^bh-1 که bh همون black node ها هسن .اما ۰ هم با این توضیحات قانع کننده نیس......
(۱۹ بهمن ۱۳۹۳ ۰۲:۳۵ ب.ظ)navid_itboy نوشته شده توسط:(19 بهمن ۱۳۹۳ ۰۲:۲۵ ب.ظ)hamedmohsenee نوشته شده توسط: بزارین تحلیل ایدین نصیری شرق رو توی ۶۰۰ مساله ببینیم:
البته قبلش باید قانونای حاکم بر درخت قرمز سیاهو بدونی:
نصیری شرق برای ۱۲۸ نود نوشته:
درختی که تمام گره های آن سیاه است باید تمام مسیرهای از ریشه تا برگ آن هم طول بوده و درنتیجه کامل است.از سوی دیگر می دانیم تعداد گره های یک درخت کامل برابر ۲ به توان k منهای یک است و ۱۲۸=۲به توان ۷
این الان یعنی چی؟؟؟؟جالبه چیزیو به چیز دیگری ربط دادین...من خودم حس میکنم ۱۰ نمیشه چون ۱۰ حداقل تعداد گره سیاهه اگر ۱۰۲۳ نود داشته باشیم با توجه به فرمول n=2^bh-1 که bh همون black node ها هسن .اما ۰ هم با این توضیحات قانع کننده نیس......
یکی از مفاهیم قرمز سیاه سیاه ارتفاع هر درخته که تعداد نودهای سیاه اون نوده تا رسیدن به یک برگ و در هر مسیر از اون نود تا یک برگ باید برابر باشن.
می دونیم د.د.ج که متوازنه و ۱۰۲۳ تا گره داره حتما یه درخت کامله.الان اگر بخوایم از ریشه به هرکدوم از برگها بریم مسیرها تماما یک اندازه ان و هنگام رنگ آمیزی دیگه هیچ نیازی نخواهد بود که نود قرمزی اضافه کنیم تا سیاه ارتفاع ریشه رو جور کنیم.توی فرایند رنگ امیزی هر نودی رو که قرمز کنیم سیاه ارتفاع ریشه درخت به هم خواهد ریخت
به هنظر من اگر نحوه رنگ امیزی قرمزسیاهو مطالعه کنیم متوجه خواهیم شد
(۱۹ بهمن ۱۳۹۳ ۰۲:۴۴ ب.ظ)hamedmohsenee نوشته شده توسط:(19 بهمن ۱۳۹۳ ۰۲:۳۵ ب.ظ)navid_itboy نوشته شده توسط:(19 بهمن ۱۳۹۳ ۰۲:۲۵ ب.ظ)hamedmohsenee نوشته شده توسط: بزارین تحلیل ایدین نصیری شرق رو توی ۶۰۰ مساله ببینیم:
البته قبلش باید قانونای حاکم بر درخت قرمز سیاهو بدونی:
نصیری شرق برای ۱۲۸ نود نوشته:
درختی که تمام گره های آن سیاه است باید تمام مسیرهای از ریشه تا برگ آن هم طول بوده و درنتیجه کامل است.از سوی دیگر می دانیم تعداد گره های یک درخت کامل برابر ۲ به توان k منهای یک است و ۱۲۸=۲به توان ۷
این الان یعنی چی؟؟؟؟جالبه چیزیو به چیز دیگری ربط دادین...من خودم حس میکنم ۱۰ نمیشه چون ۱۰ حداقل تعداد گره سیاهه اگر ۱۰۲۳ نود داشته باشیم با توجه به فرمول n=2^bh-1 که bh همون black node ها هسن .اما ۰ هم با این توضیحات قانع کننده نیس......
یکی از مفاهیم قرمز سیاه سیاه ارتفاع هر درخته که تعداد نودهای سیاه اون نوده تا رسیدن به یک برگ و در هر مسیر از اون نود تا یک برگ باید برابر باشن.
می دونیم د.د.ج که متوازنه و ۱۰۲۳ تا گره داره حتما یه درخت کامله.الان اگر بخوایم از ریشه به هرکدوم از برگها بریم مسیرها تماما یک اندازه ان و هنگام رنگ آمیزی دیگه هیچ نیازی نخواهد بود که نود قرمزی اضافه کنیم تا سیاه ارتفاع ریشه رو جور کنیم
به هنظر من اگر نحوه رنگ امیزی قرمزسیاهو مطالعه کنیم متوجه خواهیم شد
ایول این قانعم کرد مرسییییییییی دادا
(۱۸ بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ)flowerirani نوشته شده توسط: ۳۷) گزینه ۲
۳۸) گزینه یم ایینه ایی
۳۹) ۸ تا چون باید از اونیکه سرجاشه شروع کنی ۳! +۲تا هم جایگشت اون ۳تا میشه ۸
۴۰) چون گفته حداقل میشه صفر چون همشو سیاه میذاریم
۴۱) n گزینه ۲
۴۲) گزینه یک
۴۳) گزینه دو
۴۴) چهار
۴۵) ؟
۴۶) گزینه یک صفر هیچی درست نیست
۴۷) این سوال ظاهر اهمه ملت و خودم تو هپروت بودیم میشه گزینه چهار چرا؟
چون با قضیه مستر میشد ۲به توان یک اونم ۲به توان ۲
میشد n/m یعنی ۱/۲ میومد بیرون و اونم میشد رادیکال ان= n به توان ۱/۲
اخرش باید ضرب در یه logبشه میشه رادیکال ان لوگ ان واقعا وقتی من اینو نزدم حقم نیست قبول بشم
۴۸) گزینه دو ۷۲
۴۲///گزینه ۲ نمیشه؟!!
(۱۹ بهمن ۱۳۹۳ ۰۲:۵۹ ب.ظ)الی بانو نوشته شده توسط:(18 بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ)flowerirani نوشته شده توسط: ۳۷) گزینه ۲
۳۸) گزینه یم ایینه ایی
۳۹) ۸ تا چون باید از اونیکه سرجاشه شروع کنی ۳! +۲تا هم جایگشت اون ۳تا میشه ۸
۴۰) چون گفته حداقل میشه صفر چون همشو سیاه میذاریم
۴۱) n گزینه ۲
۴۲) گزینه یک
۴۳) گزینه دو
۴۴) چهار
۴۵) ؟
۴۶) گزینه یک صفر هیچی درست نیست
۴۷) این سوال ظاهر اهمه ملت و خودم تو هپروت بودیم میشه گزینه چهار چرا؟
چون با قضیه مستر میشد ۲به توان یک اونم ۲به توان ۲
میشد n/m یعنی ۱/۲ میومد بیرون و اونم میشد رادیکال ان= n به توان ۱/۲
اخرش باید ضرب در یه logبشه میشه رادیکال ان لوگ ان واقعا وقتی من اینو نزدم حقم نیست قبول بشم
۴۸) گزینه دو ۷۲
۴۲///گزینه ۲ نمیشه؟!!
۱ درسته زیرا یک بار میانه رو بدست اورده و انرا افراز کرده و k کوچکترین را هم مرتب میکنید که ازدنجایی هم که میان و افراز مرتبه ی n هسن
و مرتب سازی هم klogk می باشد در کل n +klogk