صفحه‌ها: ۱ ۲
BST نمی تونه عنصر تکراری داشته باشه
درج هر گره در bst تقریبا میشه lgn
بنابراین درج کل گره ها میشه nlogn
حتی اگه عناصر تکراری درج نکنیم زیرا تمام عناصر داره مقایسه میشه پس همون nlgn هست.به شرطی که گره های تکراری شامل دو آیتم باشن یکی مقدار و یکی تعداد تکرار
---
البته روش های counting و radix رو نمیدونم
--
اینم توضیحات ویکی پدیا:
درج یک عنصر در یک درخت جستجوی دودویی به طور میانگین از مرتبه((O(log(n است. [۱] بنابراین ساخت یک درخت جستجوی دودویی با n عضو از مرتبه((O(n log(n می‌باشد که یک درخت جستجو می‌سازدو همچنین یک مرتب سازی بهینه است.
بدترین حالت
اضافه کردن ک عنصر جدید به یک درخت جستجوی دودویی از(O(n زمان میبرد.یعنی هنگامی که درخت شبیه به یک لیست پیوندی ساده می‌شود باعث می‌شود که در بدترین حالت این الگوریتم از مرتبه (O(n۲ زمان میبرد.
البته با استفاده از گسترش هایی از درخت دودویی جستجو می‌توان رفتار بدترین حالت را بهبود داد و در بدترین حالت هم از((O(n log(n باشد. پس مرتب سازی درختی به لحاظ تئوری هم بهینه است.
---
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگه دوستان دیگه نظری دارن بگن تا بازم مطالعه کنیم
------
[undefined=undefined]
(16 بهمن ۱۳۹۱ ۰۶:۴۴ ب.ظ)armin_b00ter نوشته شده توسط: برای حل این سوال می تونید از به BST استفاده کنید و عناصر رو به ترتیب وارد BST کنید.فقط فرقی که داره اینه که وقتی یه عنصر تکراری وارد می کنید به جای اینکه اون رو ندیده بگیرید در نود مورد نظرش به یه عدد در نظر می گیرید و هر بار که تکرار شد یکی به اون عدد اضافه می کنید. ارتفاع این درخت به طور میانگین میشه logk. اگرم میگید که درخت مورب بشه میشه k می تونید از درخت AVL استفاده کنید. پس مجموعا n عنصر رو وارد می کنید و ارتفاع درخت هم متناسب با logk هست پس وارد کردنش در درخت میشه nlogk. در نهایت هم می تونید با یه پیمایش میانترتیب روی درخت مرتب شده ی اعداد رو به دست بیارید با این تفاوت که هر بار که میخواید مقدار نود رو چاپ کنید به تعدادی که در اون نود مشخص شده عدد رو چاپ می کنید که میشه n.
پس مجموعا میشه n + nlogk که میشه nlogk
--
n + nlogk میشه n ضربدر ( lgk به توان ۲)
(۱۷ بهمن ۱۳۹۱ ۰۳:۰۵ ق.ظ)csharpisatechnology نوشته شده توسط: n + nlogk میشه n ضربدر ( lgk به توان ۲)فکر کنم زیادی رابطه ی بازگشتی خوندیا c# جان
این میشه همون nlogk.(17 بهمن ۱۳۹۱ ۰۱:۵۹ ق.ظ)csharpisatechnology نوشته شده توسط: BST نمی تونه عنصر تکراری داشته باشهخوب منم نگفتم تکراری داشته باشه گفتم از وجود تکراری ها چجوری استفاده کنیم. در هر صورت واسه درج مجبوربم داخل درخت جستجو کنیم.
(۱۷ بهمن ۱۳۹۱ ۰۳:۰۵ ق.ظ)csharpisatechnology نوشته شده توسط: درج هر گره در bst تقریبا میشه lgnبا توجه به همون قضیه که خودت گفتی تکراریا درج نمیشه logn واسه وقتی هست که تمامی مقادیر متفاوت هستند و ما n مقدار تو درخت داریم ولی چون تو این حالت k مقدار مختلف داریم میشه logk.
rmin_b00ter : فکر کنم زیادی رابطه ی بازگشتی خوندیا c# جان Big Grin این میشه همون nlogk.
-----------
دوست من قضیه ی مستر رو کامل بلدم.
شاید تست رو بد ج داده باشم و جواب تست یه چیز دیگه باشه اما
N+NLGK یک حالت تعمیم در قضیه ی مستر هست که میشه N(LGK)^2
----
کتب مختلف و هادی یوسفی و قدسی و clrs و سپاهان هم همینو میگن.
جواب این سوالو هنوز نمی دونم
اما اگه k عنصر رو به جای غیر تکراری می گفت تکراری و مستقل از n،
جواب میشد nlgn که من می گم.
اینی که شما می گید جواب تست میشه nlgk فکر کنم درسته چون به نظرم آشناست ولی شک دارم.
اما اون پیچیدگی زمانی رو درست حل کردم
(۱۸ بهمن ۱۳۹۱ ۰۳:۳۳ ق.ظ)csharpisatechnology نوشته شده توسط: N+NLGK یک حالت تعمیم در قضیه ی مستر هست که میشه N(LGK)^2نه عزیزم اگه T(n) = 2T(n/2) + nlogn بود میشد اون چیزی که تو میگی. ولی اینجا رابطه ی بازگشتی نداریم که. واسه همین می گم قاطی کردی
اینجا داریم o(n) + o(nlogk) که میشه o(nlogk)
اون قضیه ی مستر که رابطه ی بازگشت بود رو هم بعد از اینکه حل می کردیم میشه o_n+o_nlgk
بعدش همینی که من می گفتم میشد.
--
شما بگو نمونه ی این سوال توی کدوم کتاب حل شده و روش دیگه ای داره یا نه.
حیف که فردا دیگه امتحانه با پس فردا.
نمی دونم دیگه چی بخونیم
(۱۸ بهمن ۱۳۹۱ ۱۱:۵۵ ق.ظ)csharpisatechnology نوشته شده توسط: اون قضیه ی مستر که رابطه ی بازگشت بود رو هم بعد از اینکه حل می کردیم میشه o_n+o_nlgkوالا قضیه ی مستر همه جا همین طوره دیگه . تو کتاب پارسه و مقسمی که من دیدم حداقل همین جوره. آقا تو نمادای مرتبه اجرایی رو با رابطه بازگشتی قاطی کردی. برو یه نگاهی بهشون بنداز. حتما فراموشت شده. مسئله ی مهمی نیست.
بعدش همینی که من می گفتم میشد.
--
شما بگو نمونه ی این سوال توی کدوم کتاب حل شده و روش دیگه ای داره یا نه.
حیف که فردا دیگه امتحانه با پس فردا.
نمی دونم دیگه چی بخونیم
(۱۶ بهمن ۱۳۹۱ ۰۶:۴۴ ب.ظ)armin_b00ter نوشته شده توسط: برای حل این سوال می تونید از به BST استفاده کنید و عناصر رو به ترتیب وارد BST کنید.فقط فرقی که داره اینه که وقتی یه عنصر تکراری وارد می کنید به جای اینکه اون رو ندیده بگیرید در نود مورد نظرش به یه عدد در نظر می گیرید و هر بار که تکرار شد یکی به اون عدد اضافه می کنید. ارتفاع این درخت به طور میانگین میشه logk. اگرم میگید که درخت مورب بشه میشه k می تونید از درخت AVL استفاده کنید. پس مجموعا n عنصر رو وارد می کنید و ارتفاع درخت هم متناسب با logk هست پس وارد کردنش در درخت میشه nlogk. در نهایت هم می تونید با یه پیمایش میانترتیب روی درخت مرتب شده ی اعداد رو به دست بیارید با این تفاوت که هر بار که میخواید مقدار نود رو چاپ کنید به تعدادی که در اون نود مشخص شده عدد رو چاپ می کنید که میشه n.
پس مجموعا میشه n + nlogk که میشه nlogk
کاملا حرف شما صحیحه. ایشون احتمالا این موردو با روابط بازگشتی قاطی کردن.
nlogk دارای رشد بیشتریه و در nهای زیاد می تونیم بجای nlogk+n
nlogk رو درنظر بگیریم.
آیا این روش قابل حل با هش نیست؟ اگر زمان دستیابی به هر عنصر در هش o(1) باشه اون موقع می تونیم با o(n) داده ها را پیمایش کنیم و بر اساس تابع هش در خونه موردنظر اضافه کنیم. هر خونه در هش هم یک شمارنده است و هر بار با مراجعه به اون یکی بهش اضافه کنیم. در یک آرایه A هم در حین پیمایش اعداد، بر اساس شمارنده شان که اگر صفر بود پس عدد مجزایی است و بنابراین آن را به این آرایه اضافه می کنیم و درغیر این صورت خیر. در آخر آرایه A را مرتب می کنیم که با klogk قابل انجام است و سپس بر اساس داشتن تعداد هر عدد همون تعدادو بهش اضافه می کنیم که میشه n+klogk
حالا فقط می تونیم از هش استفاده کنیم و زمان دستیابی اونو ثابت بگیریم؟
مثال n=9
۵و۵و۴و۲و۴و۵و۳و۳و۵
خوب اول اونهارو با کمک تابع هش در مکان مربوطه قرار می دیم و با پیمایش اونها به شمارنده مربوطه یکی اضافه می کنیم. همچنین اگر عدد اضافه شده دارای شمارنده صفر بود(بار اول) آن را به آرایه A اضافه می کنیم.
۲,۳,A=[5,4]
خوب حالا آرایه A رو مرتب می کنیم و سپس بر اساس تعدادشون (شمارنده) در مکان مناسب درج می کنیم.
(۱۸ بهمن ۱۳۹۱ ۰۵:۲۰ ب.ظ)mahdiii نوشته شده توسط: آیا این روش قابل حل با هش نیست؟ اگر زمان دستیابی به هر عنصر در هش o(1) باشه اون موقع می تونیم با o(n) داده ها را پیمایش کنیم و بر اساس تابع هش در خونه موردنظر اضافه کنیم. هر خونه در هش هم یک شمارنده است و هر بار با مراجعه به اون یکی بهش اضافه کنیم. در یک آرایه A هم در حین پیمایش اعداد، بر اساس شمارنده شان که اگر صفر بود پس عدد مجزایی است و بنابراین آن را به این آرایه اضافه می کنیم و درغیر این صورت خیر. در آخر آرایه A را مرتب می کنیم که با klogk قابل انجام است و سپس بر اساس داشتن تعداد هر عدد همون تعدادو بهش اضافه می کنیم که میشه n+klogkروش شما درست نیست چون ما از عناصر داخل آرایه اطلاعی نداریم و فکر نمی کنیم بشه تابع هشی ارائه داد که بتونه هر عنصر حتما به یه خونه مجزا نگاشت کنه و اینجوری ممکنه عنصری وجود داشته باشه که تکراری نیست ولی به خاطر برخورد در هش اونو تکراری در نظر می گیریم و در مجموع اگه ۲تا عنصر به یه خونه نگاشت بشه نمی تونیم بگیم که کدومشون تکرار شده.
(۱۸ بهمن ۱۳۹۱ ۰۶:۴۴ ب.ظ)armin_b00ter نوشته شده توسط:خوب در هش کردن، اگه اون خونه پر باشه، تو اولین خونه خالی بعدی می نویسم و نیازی نیست که از اعداد اون خبر داشته باشیم. من چندجا خوندم که می تونیم تابع هشی به دست بیاریم که با هزینه ثابت، عمل دستیابی رو انجام بده، بدون دانستن اعداد. تعداد سوالای زیادیم دیدم که با هش اومدن حل کردن و اطلاعی هم از اعداد نداشتند(18 بهمن ۱۳۹۱ ۰۵:۲۰ ب.ظ)mahdiii نوشته شده توسط: آیا این روش قابل حل با هش نیست؟ اگر زمان دستیابی به هر عنصر در هش o(1) باشه اون موقع می تونیم با o(n) داده ها را پیمایش کنیم و بر اساس تابع هش در خونه موردنظر اضافه کنیم. هر خونه در هش هم یک شمارنده است و هر بار با مراجعه به اون یکی بهش اضافه کنیم. در یک آرایه A هم در حین پیمایش اعداد، بر اساس شمارنده شان که اگر صفر بود پس عدد مجزایی است و بنابراین آن را به این آرایه اضافه می کنیم و درغیر این صورت خیر. در آخر آرایه A را مرتب می کنیم که با klogk قابل انجام است و سپس بر اساس داشتن تعداد هر عدد همون تعدادو بهش اضافه می کنیم که میشه n+klogkروش شما درست نیست چون ما از عناصر داخل آرایه اطلاعی نداریم و فکر نمی کنیم بشه تابع هشی ارائه داد که بتونه هر عنصر حتما به یه خونه مجزا نگاشت کنه و اینجوری ممکنه عنصری وجود داشته باشه که تکراری نیست ولی به خاطر برخورد در هش اونو تکراری در نظر می گیریم و در مجموع اگه ۲تا عنصر به یه خونه نگاشت بشه نمی تونیم بگیم که کدومشون تکرار شده.
(۱۸ بهمن ۱۳۹۱ ۰۷:۱۸ ب.ظ)mahdiii نوشته شده توسط: خوب در هش کردن، اگه اون خونه پر باشه، تو اولین خونه خالی بعدی می نویسم و نیازی نیست که از اعداد اون خبر داشته باشیم. من چندجا خوندم که می تونیم تابع هشی به دست بیاریم که با هزینه ثابت، عمل دستیابی رو انجام بده، بدون دانستن اعداد. تعداد سوالای زیادیم دیدم که با هش اومدن حل کردن و اطلاعی هم از اعداد نداشتندخب اگه بخوایم زنجیره داشته باشیم که دیگه o(1) نمیشه. در بدترین حالت مجموعا میشه o(nk) که از o(nlogk) بیشتره.
من نگفتم بدترین حالتش میشه هزینه ثابت. مشخصه که بدترین حالتش میشه O(n) برای هر کدوم اما شما به این عکس نگاه کنید. همون طوری که مشخصه در حالت متوسط هزینه ثابته. تو این مساله هم نگفته بدترین حالت، پس به طور معمول باید حالت متوسطو درنظر بگیریم.
حالت متوسط دستیابی در هش نوشته :
[tex]1 \frac{n}{k}[/tex]
که اگه تعداد خونه هارو با تعداد عنصرهایی که می خواهیم در اون قرار بدیم برابر بگیریم میشه o(2) یعنی همون ثابت
(۱۸ بهمن ۱۳۹۱ ۰۸:۰۰ ب.ظ)mahdiii نوشته شده توسط: من نگفتم بدترین حالتش میشه هزینه ثابت. مشخصه که بدترین حالتش میشه O(n) برای هر کدوم اما شما به این عکس نگاه کنید. همون طوری که مشخصه در حالت متوسط هزینه ثابته. تو این مساله هم نگفته بدترین حالت، پس به طور معمول باید حالت متوسطو درنظر بگیریم.این حرف شما درسته و این حالت میانگین هم کاملا درسته چون در حالت میانگین هر زنجیره طول n\k داره. اما شما در صورتی می تونین حالت میانگین رو در نظر بگیرید که پراکندگی اعداد جوری باشه که به صورت یکنواخت تو جدول توزیع بشه. ولی با توجه به اینکه ممکنه این حالت پیش نیاد و احتمالش هم زیاده نمی تونیم حالت میانگین رو در نظر بگیریم. در ضمن در AVL هم ما تو بدترین حالت logk رو داریم و اون رو هم تو بدترین حالت باید در نظر بگیریم.
حالت متوسط دستیابی در هش نوشته :
[tex]1 \frac{n}{k}[/tex]
که اگه تعداد خونه هارو با تعداد عنصرهایی که می خواهیم در اون قرار بدیم برابر بگیریم میشه o(2) یعنی همون ثابت
ولی از این حرفا گذشته تو این سوال هم گزینه ی n وجود نداره اصلا. پس بهتره که با بحثای اضافی اون بنده های خدا که میان اینارو می خونن در آینده گیج نکنیم
