۰
subtitle
ارسال: #۱
  
اشتراک لیست
جواب این سوال چی میشه ؟؟؟؟
۰
ارسال: #۲
  
RE: اشتراک لیست
فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex]
ارسال: #۳
  
RE: اشتراک لیست
(۰۹ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)mfXpert نوشته شده توسط: فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex]تو بدترین حالت خودم هم همین رو بدست آوردم اما مشکل من تو حالت میانگینه که نمیدونم میشه همون nlognیا n حالت میانگین رو چه جوری در نظر بگیریم؟؟؟؟
۰
ارسال: #۴
  
اشتراک لیست
نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟
ارسال: #۵
  
RE: اشتراک لیست
(۰۹ دى ۱۳۹۰ ۰۱:۱۱ ب.ظ)NoOne نوشته شده توسط: نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....تست اول ساختمان داده ۹۰ بوده
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟
اینی که شما میگید حداقل nlog n هست (البته جواب رو به ما میده )
فکر کنم ۲ بشه . اونایی که کتاب سنجش رو دارن لطفا جواب کتاب رو بزارن تا بررسی کنیم.
۰
ارسال: #۷
  
RE: اشتراک لیست
۰
۰
ارسال: #۹
  
اشتراک لیست
گزینه صحیح سه هست .
محال است در این سئوال بتوان به مرتبه ایی بهتر از nlgn دست یافت چه میانگین و چه بدترین حالت .
اصلا به راحتی میتوان اثبات کرد که الگوریتمی که بر مبنای مقایسه پایه ریزی شده باشه نمیتواند در زمان کمتر از nlgn اشتراک این دولیست را به دست اورد .
شاید طراح محترم فراموش کار بودن و یا این نکته رو فراموش کردن و یا اینکه خواستن به دواطلبان کنکور ۹۰ حال درست و حسابی بدن .
جای بسی تاسف هست شاهد چنین مواردی هستیم که در یک سال دو تا سئوال از پنج تا سئوال ساختمان حذف بشه . این هم به نحوی حق ناس هست که حق هزاران نفر رو پایمال میکنه .
در حالت خاص میتوان به مرتبه n دست یافت اما این فقط در حالت خاص امکان پذیر هست و با روشهایی شبیه الگوریتمهای مرتب سازی خطی و غیره (مثلا با باکت بندی مناسب یا حتی در هم سازی) اما مسئله اینه که این تنها در حالتهای خاص امکان پذیر هست و زمانی که هر دولیست ما از یکی الگو خاص پیروی کنن . که در اینجا هیچ اطلاعی از عناصر لیست نداریم و تنها راه همان مرتب سازی در زمان Nlgn ودر نهایت بقیه ماجرا
محال است در این سئوال بتوان به مرتبه ایی بهتر از nlgn دست یافت چه میانگین و چه بدترین حالت .
اصلا به راحتی میتوان اثبات کرد که الگوریتمی که بر مبنای مقایسه پایه ریزی شده باشه نمیتواند در زمان کمتر از nlgn اشتراک این دولیست را به دست اورد .
شاید طراح محترم فراموش کار بودن و یا این نکته رو فراموش کردن و یا اینکه خواستن به دواطلبان کنکور ۹۰ حال درست و حسابی بدن .
جای بسی تاسف هست شاهد چنین مواردی هستیم که در یک سال دو تا سئوال از پنج تا سئوال ساختمان حذف بشه . این هم به نحوی حق ناس هست که حق هزاران نفر رو پایمال میکنه .
در حالت خاص میتوان به مرتبه n دست یافت اما این فقط در حالت خاص امکان پذیر هست و با روشهایی شبیه الگوریتمهای مرتب سازی خطی و غیره (مثلا با باکت بندی مناسب یا حتی در هم سازی) اما مسئله اینه که این تنها در حالتهای خاص امکان پذیر هست و زمانی که هر دولیست ما از یکی الگو خاص پیروی کنن . که در اینجا هیچ اطلاعی از عناصر لیست نداریم و تنها راه همان مرتب سازی در زمان Nlgn ودر نهایت بقیه ماجرا
۰
ارسال: #۱۰
  
اشتراک لیست
در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره
ارسال: #۱۱
  
RE: اشتراک لیست
(۱۳ دى ۱۳۹۰ ۰۸:۲۳ ب.ظ)rad.bahar نوشته شده توسط: در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره
در مورد راه حلش توضیحی نداده ؟؟؟
۰
ارسال: #۱۲
  
RE: اشتراک لیست
فکر کنم این طوری حل بشه
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۱۳
  
اشتراک لیست
خب شاید از مرتب سازی مبنایی استفاده کرده
اگه نه علتش رو بگید
ازمون حالت میانگین و بدترین رو خواسته
اگه نه علتش رو بگید
(۱۹ بهمن ۱۳۹۰ ۰۸:۰۸ ب.ظ)saeedeh123 نوشته شده توسط: فکر کنم این طوری حل بشه
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ازمون حالت میانگین و بدترین رو خواسته
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
پیدا کردن اشتراک دو ارایه | shayesteNEY | ۶ | ۵,۷۸۰ |
۰۸ دى ۱۳۹۳ ۰۳:۱۵ ق.ظ آخرین ارسال: shayesteNEY |
|
پیدا کردن اشتراک دو آرایه نا مرتب (کامپیوتر ٩٠) | Amir V | ۶ | ۳,۴۵۶ |
۰۵ بهمن ۱۳۹۱ ۰۷:۵۸ ب.ظ آخرین ارسال: ۸Operation |
|
لیست مجاورتی ؟؟؟ | jafarir | ۲ | ۱,۹۴۵ |
۲۵ آذر ۱۳۹۱ ۰۹:۴۲ ق.ظ آخرین ارسال: jafarir |
|
لیست مجاورتی | homa | ۱ | ۲,۳۰۷ |
۱۳ آذر ۱۳۹۰ ۰۹:۱۷ ب.ظ آخرین ارسال: مازیار صفایی |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close