تالار گفتمان مانشت
مرتبه ی زمانی ادغام k لیست مرتب شده - نسخه‌ی قابل چاپ
مرتبه ی زمانی ادغام k لیست مرتب شده - mostafaheydar1370 - 07 آبان ۱۳۹۵ ۰۵:۴۵ ب.ظ

سلام دوستان
ما K لیست مرتب شده داریم که می خواهیم انها را در هم ادغام کنیم ایا طبق الگوریتم زیر مرتبه ی زمانی ان [tex]O(N)[/tex](مقدار N : تعداد کل عناصر K لیست)می تواند باشد
به این صورت که برای هر یک از K لیست یک اشاره گر به ابتدای هر یک از K لیست قرار می دهیم و با یک حلقه ی به طول N در هرمرحله عنصری از i امین k لیست را انتخاب می کنیم که بزرگترین مقدار عنصر در موقیعت اشاره گرهای k لیست داشته باشد و سپس اشاره گر را یک واحد جلو میبریم به همین صورت تا اخر .اگر این روش صحیح هست چرا در بعضی جاها نوشته شده است که ادغام kلیست مرتب شده از مرتبه ی [tex]Nlog(k)[/tex] است ؟
شبه کد حل مسئله :
[tex]for(i\: to\: N)\:
select\: max\: \&p[j]\:
print\: \&p[j]\:
++j[/tex]
ممون بابت توجه تون

RE: مرتبه ی زمانی ادغام k لیست مرتب شده - Behnam‌ - ۰۷ آبان ۱۳۹۵ ۰۶:۱۶ ب.ظ

(۰۷ آبان ۱۳۹۵ ۰۵:۴۵ ب.ظ)mostafaheydar1370 نوشته شده توسط:  سلام دوستان
ما K لیست مرتب شده داریم که می خواهیم انها را در هم ادغام کنیم ایا طبق الگوریتم زیر مرتبه ی زمانی ان [tex]O(N)[/tex](مقدار N : تعداد کل عناصر K لیست)می تواند باشد
به این صورت که برای هر یک از K لیست یک اشاره گر به ابتدای هر یک از K لیست قرار می دهیم و با یک حلقه ی به طول N در هرمرحله عنصری از i امین k لیست را انتخاب می کنیم که بزرگترین مقدار عنصر در موقیعت اشاره گرهای k لیست داشته باشد و سپس اشاره گر را یک واحد جلو میبریم به همین صورت تا اخر .اگر این روش صحیح هست چرا در بعضی جاها نوشته شده است که ادغام kلیست مرتب شده از مرتبه ی [tex]Nlog(k)[/tex] است ؟
شبه کد حل مسئله :
[tex]for(i\: to\: N)\:
select\: max\: \&p[j]\:
print\: \&p[j]\:
++j[/tex]
ممون بابت توجه تون

بدون ورود به جزئیات، روش شما اشتباه هست به خاطر اینکه فرض k=n، یعنی شما n لیست مرتب شده دارید و بالطبع طول هر لیست ۱ خواهد شد (یعنی اصلاً اعداد مرتب نشده‌اند. به هر حال این هم حالت خاصی هست). در این صورت شما می‌گید الگوریتم شما از مرتبه‌ی n می‌تونه اینا رو مرتب کنه در حالی که الگوریتم‌های مرتب‌سازی ار مرتبه‌ی nlogn بهتر نیستند. یا مثلاً فرض کنید [tex]\frac{n}{2}[/tex] لیست مرتب شده دارید (پس هر لیست دو عنصر داره). باز این در مرتبه‌ی [tex]nlogk=nlog(\frac{n}{2})=\theta(nlogn)[/tex] مرتب میشه ولی شما می‌گید که n/2 عدد رو (حتی فرض کنیم هر لیست یک دونه عدد داره) با مرتبه‌ی n می‌تونید merge کنید که اشتباه هست.

در مورد جزئیات روشتون هم، شما هر بار، بزرگترین عدد رو بین اون K لیست پیدا و چاپ می‌کنید، بقیه‌ی اعداد چی؟ فرض کنیم ۳ تا لیست داریم و بعد از دو مرحله، شما دو تا عدد بزرگ رو چاپ کردید (از بین ۶ عدد در ۳ لیست). ولی ۴ عدد مونده که ترتیب اون‌ها رو نمیشه حدس زد.
از هرم برای ادغام لیست‌های مرتب شده استفاده می‌کنند که اونم مرتبه‌ی [tex]nlogk[/tex] هست که گفتید و در کنکور هم اومده بود.

RE: مرتبه ی زمانی ادغام k لیست مرتب شده - mostafaheydar1370 - 07 آبان ۱۳۹۵ ۱۰:۴۳ ب.ظ

(۰۷ آبان ۱۳۹۵ ۰۶:۱۶ ب.ظ)Behnam‌ نوشته شده توسط:  
(07 آبان ۱۳۹۵ ۰۵:۴۵ ب.ظ)mostafaheydar1370 نوشته شده توسط:  سلام دوستان
ما K لیست مرتب شده داریم که می خواهیم انها را در هم ادغام کنیم ایا طبق الگوریتم زیر مرتبه ی زمانی ان [tex]O(N)[/tex](مقدار N : تعداد کل عناصر K لیست)می تواند باشد
به این صورت که برای هر یک از K لیست یک اشاره گر به ابتدای هر یک از K لیست قرار می دهیم و با یک حلقه ی به طول N در هرمرحله عنصری از i امین k لیست را انتخاب می کنیم که بزرگترین مقدار عنصر در موقیعت اشاره گرهای k لیست داشته باشد و سپس اشاره گر را یک واحد جلو میبریم به همین صورت تا اخر .اگر این روش صحیح هست چرا در بعضی جاها نوشته شده است که ادغام kلیست مرتب شده از مرتبه ی [tex]Nlog(k)[/tex] است ؟
شبه کد حل مسئله :
[tex]for(i\: to\: N)\:
select\: max\: \&p[j]\:
print\: \&p[j]\:
++j[/tex]
ممون بابت توجه تون

بدون ورود به جزئیات، روش شما اشتباه هست به خاطر اینکه فرض k=n، یعنی شما n لیست مرتب شده دارید و بالطبع طول هر لیست ۱ خواهد شد (یعنی اصلاً اعداد مرتب نشده‌اند. به هر حال این هم حالت خاصی هست). در این صورت شما می‌گید الگوریتم شما از مرتبه‌ی n می‌تونه اینا رو مرتب کنه در حالی که الگوریتم‌های مرتب‌سازی ار مرتبه‌ی nlogn بهتر نیستند. یا مثلاً فرض کنید [tex]\frac{n}{2}[/tex] لیست مرتب شده دارید (پس هر لیست دو عنصر داره). باز این در مرتبه‌ی [tex]nlogk=nlog(\frac{n}{2})=\theta(nlogn)[/tex] مرتب میشه ولی شما می‌گید که n/2 عدد رو (حتی فرض کنیم هر لیست یک دونه عدد داره) با مرتبه‌ی n می‌تونید merge کنید که اشتباه هست.

در مورد جزئیات روشتون هم، شما هر بار، بزرگترین عدد رو بین اون K لیست پیدا و چاپ می‌کنید، بقیه‌ی اعداد چی؟ فرض کنیم ۳ تا لیست داریم و بعد از دو مرحله، شما دو تا عدد بزرگ رو چاپ کردید (از بین ۶ عدد در ۳ لیست). ولی ۴ عدد مونده که ترتیب اون‌ها رو نمیشه حدس زد.
از هرم برای ادغام لیست‌های مرتب شده استفاده می‌کنند که اونم مرتبه‌ی [tex]nlogk[/tex] هست که گفتید و در کنکور هم اومده بود.
بله شما درست میگید اشتباه من این بود که kمقایسه برای پیدا کردن ماکزیمم درون لیست ها رو در نطر نگرفته بودم (دراصل حواسم نبود که Kمتغیر هست ومن اون رو ثابت فرض کرده بودم و می گفتم ثابت در متغیر میشه ثابت که میشد (O(nو اشتباه بود )و میشدNK)O)ولی نمی دونم چطوری میشه (O(Nlogkکه باید روش فکر کنم.