فکر می کنم جوابش گزینه ۲ بشه!درسته؟!
با استفاده از یه BST که تعداد تکراری ها رو برای هر اندیس میشماره در همین مرتبه درج میکنیم و بعد LDR پیمایش می کنیم.
البته از هش هم فک کنم بشه حلش کرد!

پاسخ ساده هست
ببینید
اگر n عنصر متمایز بود پاسخ میشد nlogn
ولی حالا k دسته داریم که رویهم میشن n تا
خب من میام این k ارایه درست میکنم و به کمک این k ارایه یک درخت میسازم خب حالا این میشه درخت انتخابی و هربار مینیم را با logkارتفاع درخت پیدا میکنم چون n عنصر هست میشه nlogk
۵ دقیقه روش فکر کردم سوال جلبی بود کتابها فقط گفتن جواب میشه nlogk و راه حل نگفتن

(۱۱ بهمن ۱۳۹۱ ۱۲:۳۲ ق.ظ)teacherpc نوشته شده توسط:  اگر n عنصر متمایز بود پاسخ میشد nlogn
ولی حالا k دسته داریم که رویهم میشن n تا
خب من میام این k ارایه درست میکنم و به کمک این k ارایه یک درخت میسازم خب حالا این میشه درخت انتخابی و هربار مینیم را با logkارتفاع درخت پیدا میکنم چون n عنصر هست میشه nlogk

میشه خواهشا یه کم بیشتر توضیح بدین؟
ساخت درخت جستجوی دودویی از مرتبهn هست.ولی وقتی به جای هر راس درخت از یک آرایه استفاده بشه، اونوقت مرتبه اش n^2نمیشه؟
در واقع سوالم اینه که چه جوری nتا اعداد اولیه رو بذاریم تو درخت به ارتفاعk ؟
پیشاپیش ممنون

ببنینید ساخت درخت جستجوی دودویی میشه nlogn
دربدترین حالت میشه nدو
اما اینجا عناصر n تا هستند که تو k دسته تقسیم میشن مثلن اگه بیست تا عدد باشن ۴ تا ۵ داریم ۴ تا ۶ داریم ۴ تا ۱۲ داریم
۴ت ۹ داریم ۴تا ۱۰ داریم خب حالا n=20 , و k=5هست مثل اینه که بگن تمام بچه های مهدکودک رو تو k تا صف مرتب کن که هم قدها تو یک صف باشن و k نفر با قدهای متمایز باشه!

---

قرارنیست n تا عدد رو بزاریم تو درخت به ارتفاع k
ما k تا ارایه میزاریم کنارهم هرسری عنصراول هرکدوم با بقیه مقایسه میشه و در ارابه نهایی فرار میگیره
شبیه درخت انتخابی میشه متوجه شدین؟

آره اشتباه کردم.حواسم نبود.
مرسی از توضیحاتتون.
من فقط یه نکته ای که متوجه نمیشم:
اینکه گفتین هر سری عنصر اول k آرایه با بقیه مقایسه میشه.
اخه ارایه اولیه n تایی، نا مرتب هست.
مثلا میشه لطفا برای اعداد زیر الگوریتمو اجرا کنین:
۵,۹,۸,۸,۸,۶,۵,۹,۸,۹,۵,۶,۹,۵,۶,۶
در اینجا n برابر ۱۶ هست و k هم ۴ هست.
خب حالا این ۱۶ تا روبه ۴ ارایه ۴تایی تقسیم میکنیم،درسته؟
اونوقت اگر عنصر اول این چهار آرایه باهم مقایسه بشه و در ارایه نهایی قرار بگیره، ممکنه آرایه نهایی مرتب نباشه.


کلا نمیدونم چرا گیج شدم.

ظرفیت k تا ارایه همه یکسان هست رویهم ظرفیتشون میشه n
عناصر هر کدوم از این k ارایه مرتب نیست یعنی k تا ارایه داریم که تو خودشون هم نامرتب هستند
خب حالا ما با عناصر بالای ارایه های (k تا ارایه رو به شکل پشته تصور کن که از بالای هرکدوم یه عنصر میاد بیرون و یه درخت ساخته میشه با عنصر شماره یکم بالای این k ارایه ) خب بعد از اینکه درخت ساخته شد دیگه کار تمامه هر بار هر ارایه ای که مینیمم بود عنصربالای خودش(به شکل پشته تصور کنیدش برااینکه متوجه شید ولی پشته نیستا حواست باشه!) را میفرسته تو درخت و این عنصر ارتفاع درخت رو طی میکنه(min تزریق میشه تو درخت ) و چون n عنصر داریم هر عنصر مجبوره از ارتفاع درخت طی کنه هر عنصری زودتر رسید به ریشه در ارایه نهایی قرار میگیره نهایتن همه مرتب میشن
اگه متوجه نشدین بگید تا بیشتر توضیح بدم
(ظرفیت k ارایه میتونه یکسان نباشه برا فهم بیشتر اول بحث اینجوری توضیح دادم که حواستون بیشتر به طرف عمق مساله جلب بشه نه جزئیات ! فکر میکنم فن بیانم خوبه اگه باز جایی متوجه نشدی بگین)

(۱۲ بهمن ۱۳۹۱ ۰۷:۰۹ ب.ظ)teacherpc نوشته شده توسط:  ظرفیت k تا ارایه همه یکسان هست رویهم ظرفیتشون میشه n
عناصر هر کدوم از این k ارایه مرتب نیست یعنی k تا ارایه داریم که تو خودشون هم نامرتب هستند
خب حالا ما با عناصر بالای ارایه های (k تا ارایه رو به شکل پشته تصور کن که از بالای هرکدوم یه عنصر میاد بیرون و یه درخت ساخته میشه با عنصر شماره یکم بالای این k ارایه ) خب بعد از اینکه درخت ساخته شد دیگه کار تمامه هر بار هر ارایه ای که مینیمم بود عنصربالای خودش(به شکل پشته تصور کنیدش برااینکه متوجه شید ولی پشته نیستا حواست باشه!) را میفرسته تو درخت و این عنصر ارتفاع درخت رو طی میکنه(min تزریق میشه تو درخت ) و چون n عنصر داریم هر عنصر مجبوره از ارتفاع درخت طی کنه هر عنصری زودتر رسید به ریشه در ارایه نهایی قرار میگیره نهایتن همه مرتب میشن
اگه متوجه نشدین بگید تا بیشتر توضیح بدم
(ظرفیت k ارایه میتونه یکسان نباشه برا فهم بیشتر اول بحث اینجوری توضیح دادم که حواستون بیشتر به طرف عمق مساله جلب بشه نه جزئیات ! فکر میکنم فن بیانم خوبه اگه باز جایی متوجه نشدی بگین)

ممنون از وقتی که گذاشتین ولی این چیزی که شما می گین برای وقتیه که این K تا آرایمون مرتب باشن ولی اینجا که مرتب نیستند .شما از تکراری بودن عناصر آرایه چه استفاده ای تو حل کردین اگه این جوری باشه که شما میگین میشه هر آرایه ای را با nlogk مرتب کرد! اگه میشه بیشتر توضیح بدین ممنون.اگه کسه دیگه ای هم میدونه خواهشا بگه .

سپاس بیکران.

اشتباه کردید
رو صورت سوال دقت کنید ببینید باز دقت کن یه بار دیگه صورت سوال رو بخون
گفته دنباله ای از اعداد که تعدادشون n تاست ولی k عنصر متمایز داریم (k<n)اگه k تا متمایز نبودند مشکل داشتیم و اینکه میگین اگه اینطور بود هر دنباله ای رو میشد با این روش مرتب کرد اصلن صحیح نیست (اینجا k عنصر متمایز داریم نه nتا متمایز!!!! )
خب من وقتی میدونم k عنصر متمایز دارم با ساخت درخت که ارتفاعش logk هست میام تمام n عنصر رو با log مقایسه مرتب میکنم
n تا عنصر داریم با log n مقایسه برا هر عنصر داریم میشه nlogk
فکر کنم هنوز صورت سوال رو خوب متوجه نشده باشین!
براخودم هم بعضی وقتا پیش اومده وقتی یه سوال رو خوب نخوندم با هر بار خوندن نکته جدیدی تو سوال کشف کردم!
شایدم اینجا من خوب متوجه نشدم!

(۱۴ بهمن ۱۳۹۱ ۱۱:۳۷ ق.ظ)teacherpc نوشته شده توسط:  اشتباه کردید
رو صورت سوال دقت کنید ببینید باز دقت کن یه بار دیگه صورت سوال رو بخون
گفته دنباله ای از اعداد که تعدادشون n تاست ولی k عنصر متمایز داریم (k<n)اگه k تا متمایز نبودند مشکل داشتیم و اینکه میگین اگه اینطور بود هر دنباله ای رو میشد با این روش مرتب کرد اصلن صحیح نیست (اینجا k عنصر متمایز داریم نه nتا متمایز!!!! )
خب من وقتی میدونم k عنصر متمایز دارم با ساخت درخت که ارتفاعش logk هست میام تمام n عنصر رو با log مقایسه مرتب میکنم
n تا عنصر داریم با log n مقایسه برا هر عنصر داریم میشه nlogk
فکر کنم هنوز صورت سوال رو خوب متوجه نشده باشین!
براخودم هم بعضی وقتا پیش اومده وقتی یه سوال رو خوب نخوندم با هر بار خوندن نکته جدیدی تو سوال کشف کردم!
شایدم اینجا من خوب متوجه نشدم!

نه ، این چیزی که میگین درست نیست.خوب ما تکراری داشته باشیم ولی مرتب که نیست پس با درخت انتخابی نمیشه.کس دیگه ای از دوستان نظری نداره؟

این اخرین پاسخ من به این تاپیک هست شما که میگین استباهه درستش رو بزارید!
دیگه بیشتر نمیدونم من دیگه این بحث رو ادامه نمیدم
موفق باشید .

(۱۴ بهمن ۱۳۹۱ ۱۱:۳۷ ق.ظ)teacherpc نوشته شده توسط:  خب من وقتی میدونم k عنصر متمایز دارم با ساخت درخت که ارتفاعش logk هست میام تمام n عنصر رو با log مقایسه مرتب میکنم
n تا عنصر داریم با log n مقایسه برا هر عنصر داریم میشه nlogk
شایدم اینجا من خوب متوجه نشدم!

teacherpc و m-m-m
من مشکلو پیدا کردم.اشکال به صورت سوال و برداشت دوگانه از آن باز میگردد؛
راه حل teacherpc درست است به شرطی که ما از این k عدد تکراری خبر داشته باشیم، یعنی بدونیم که چهار تا عدد تکراری داریم و این اعداد مثلا ۶و ۷و ۸ و ۹ هستن.
-----------
اما وقتی فقط تعداد اعداد تکراری یا همون k رو بدونیم و اطلاعی راجع به اینکه این اعداد تکراری، چه اعدادی هستند نداشته باشیم اونوقت این راه حل جواب نمیدهد.
--------------
صورت این سوال دوپهلو است و مشخص نیست که آیا حالت اولی که توضیح دادم مدنظره یا حالت دوم.
------------------
با توجه به کلید سنجش، ظاهرا منظور طراح حالت اول بوده و در واقع ما از اینکه چه اعدادی تکراری هستن خبر داریم.
------------------
بنابراین این راه حل صحیح است که:
با k عنصر تکراری، درخت میسازیم و بعد n تا عنصر را جست و جو میکنیم(هر عنصر با logk) و در نهایت میشود nlogk.
----------------------
با سپاس از teacherpc

خوب،سوال که مشخصه وقتی نگفته میدونیم این k تا تکراری چه اعدادی هستند یعنی نمیدونیم .این که دیگه پیچوندن نداره هر چی تو سوال نگفته رو نمی دونیم چی هست.
در ضمن من اگه جواب سوالو میدونستم که اینجا مطرح نمی کردم .در ضمن آدم نباید از این که میگن راهش غلطه ناراحت بشه که

برای حل این سوال می تونید از به BST استفاده کنید و عناصر رو به ترتیب وارد BST کنید.فقط فرقی که داره اینه که وقتی یه عنصر تکراری وارد می کنید به جای اینکه اون رو ندیده بگیرید در نود مورد نظرش به یه عدد در نظر می گیرید و هر بار که تکرار شد یکی به اون عدد اضافه می کنید. ارتفاع این درخت به طور میانگین میشه logk. اگرم میگید که درخت مورب بشه میشه k می تونید از درخت AVL استفاده کنید. پس مجموعا n عنصر رو وارد می کنید و ارتفاع درخت هم متناسب با logk هست پس وارد کردنش در درخت میشه nlogk. در نهایت هم می تونید با یه پیمایش میانترتیب روی درخت مرتب شده ی اعداد رو به دست بیارید با این تفاوت که هر بار که میخواید مقدار نود رو چاپ کنید به تعدادی که در اون نود مشخص شده عدد رو چاپ می کنید که میشه n.
پس مجموعا میشه n + nlogk که میشه nlogk

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) برای هر کدوم اما شما به این عکس نگاه کنید. همون طوری که مشخصه در حالت متوسط هزینه ثابته. تو این مساله هم نگفته بدترین حالت، پس به طور معمول باید حالت متوسطو درنظر بگیریم.
حالت متوسط دستیابی در هش نوشته :
$1 \frac{n}{k}$
که اگه تعداد خونه هارو با تعداد عنصرهایی که می خواهیم در اون قرار بدیم برابر بگیریم میشه o(2) یعنی همون ثابت

(۱۸ بهمن ۱۳۹۱ ۰۸:۰۰ ب.ظ)mahdiii نوشته شده توسط:  من نگفتم بدترین حالتش میشه هزینه ثابت. مشخصه که بدترین حالتش میشه O(n) برای هر کدوم اما شما به این عکس نگاه کنید. همون طوری که مشخصه در حالت متوسط هزینه ثابته. تو این مساله هم نگفته بدترین حالت، پس به طور معمول باید حالت متوسطو درنظر بگیریم.
حالت متوسط دستیابی در هش نوشته :
$1 \frac{n}{k}$
که اگه تعداد خونه هارو با تعداد عنصرهایی که می خواهیم در اون قرار بدیم برابر بگیریم میشه o(2) یعنی همون ثابت

این حرف شما درسته و این حالت میانگین هم کاملا درسته چون در حالت میانگین هر زنجیره طول n\k داره. اما شما در صورتی می تونین حالت میانگین رو در نظر بگیرید که پراکندگی اعداد جوری باشه که به صورت یکنواخت تو جدول توزیع بشه. ولی با توجه به اینکه ممکنه این حالت پیش نیاد و احتمالش هم زیاده نمی تونیم حالت میانگین رو در نظر بگیریم. در ضمن در AVL هم ما تو بدترین حالت logk رو داریم و اون رو هم تو بدترین حالت باید در نظر بگیریم.
ولی از این حرفا گذشته تو این سوال هم گزینه ی n وجود نداره اصلا. پس بهتره که با بحثای اضافی اون بنده های خدا که میان اینارو می خونن در آینده گیج نکنیم