(۲۶ اسفند ۱۳۹۴ ۱۱:۱۹ ب.ظ)Nesyan نوشته شده توسط:  سلام
در آرایه n عنصری نامرتب، با چه مرتبه ای میتوان k عنصر کوچک آرایه را بصورت مرتب یافت؟

بهترین مرتبه اش میشه n + k logk . لطفا بگین چطوری این بدست میاد. مرسی

کافیه که عنصر k ام رو محور قرار بدید و تا عناصر کوچکتر از k ، قبل از عنصر و عناصر بزرگتر از k بعد از k قرار گیرد
مرتبه این عمل n هست
حالا باید عناصر قبل از k رو که همون عناصر کوچکتر از k هست با مرتبه klogk مرتب کنید
میشه O(n+klogk)

(۲۶ اسفند ۱۳۹۴ ۱۱:۵۱ ب.ظ)sixsixsix نوشته شده توسط:  

(26 اسفند ۱۳۹۴ ۱۱:۱۹ ب.ظ)Nesyan نوشته شده توسط:  

کافیه که عنصر k ام رو محور قرار بدید و تا عناصر کوچکتر از k ، قبل از عنصر و عناصر بزرگتر از k بعد از k قرار گیرد
مرتبه این عمل n هست
حالا باید عناصر قبل از k رو که همون عناصر کوچکتر از k هست با مرتبه klogk مرتب کنید
میشه O(n+klogk)

متوجه شدم، خیلی ممنون

(۲۶ اسفند ۱۳۹۴ ۱۱:۵۱ ب.ظ)sixsixsix نوشته شده توسط:  

(26 اسفند ۱۳۹۴ ۱۱:۱۹ ب.ظ)Nesyan نوشته شده توسط:  سلام
در آرایه n عنصری نامرتب، با چه مرتبه ای میتوان k عنصر کوچک آرایه را بصورت مرتب یافت؟

بهترین مرتبه اش میشه n + k logk . لطفا بگین چطوری این بدست میاد. مرسی

کافیه که عنصر k ام رو محور قرار بدید و تا عناصر کوچکتر از k ، قبل از عنصر و عناصر بزرگتر از k بعد از k قرار گیرد
مرتبه این عمل n هست
حالا باید عناصر قبل از k رو که همون عناصر کوچکتر از k هست با مرتبه klogk مرتب کنید
میشه O(n+klogk)

آرایه نامرتبه و ما باید ابتدا کوچکترین کلید K ام رو پیدا کنیم که اونم از مرتبه O(n) هستش بعد یه الگوریتم پارتیشن روش انجام بدیم تا عناصر کوچکتر از k یه جا جمع شن که اونم از مرنبه O(n) هستش و بعد با مرتبه klog(k) اونا رو مرتب کنیم
در کل میشه O(2n+klog(k)) که همون برابر O(n+klog(k)) هستش.

سلام
اگر قرار باشه k عنصر کوچک آرایه رو مرتب کنیم میشه n+klogk
ولی اگر قراره فقط kعنصر کوچیکو بدست بیاریم(مرتب بودنشون مهم نباشه) که با هزینه ۲n بدست میان.به این صورت که اول kامین عنصر کوچکو با هزینهn بدست میاریم و بعد عناصر کوچکتر از اونو از آرایه با هزینهn استخراج میکنیم.