سلام کسی می دونه این سوال چه جوری حل میشه ؟
(۰۴ آبان ۱۳۹۵ ۱۲:۳۰ ب.ظ)mostafaheydar1370 نوشته شده توسط: سلام کسی می دونه این سوال چه جوری حل میشه ؟
فایل‌ها رو در خود مانشت آپلود کنید. روی پیوست تازه کلیک کنید، فایل رو انتخاب و آپلود کنید، در انتها روی گزینه‌ی اضافه کردن فایل پیوست به ارسال کلیک کنید. این لینکی که گذاشتید اصلاً باز نمیشه.
با توجه به فرض سؤال میشه نوشت [tex]A[1]<A[1+K][/tex]، همینطور میشه نوشت [tex]A[1+K]<A[1+2K][/tex] و ...، در نتیجه
[tex]A[1]<A[1+K]<A[1+2K]<A[1+3K]<...<A[1+aK][/tex]. در اینجا
[tex]1+aK\approx N \longrightarrow a=\frac{N}{K}[/tex]
پس لیست اول شامل عناصر ۱ و ۱+K و ۱+۲K و ... ۱+aK هست. یعنی a+1 تا عضو داره که [tex]a=\frac{N}{K}[/tex]. فرض می‌کنیم همون a تا عضو رو داره دقیقا (در حل مسأله تأثیری نداره). همین حالت رو برای اندیس‌هایی که از ۲ شروع بشن هم داریم و ...
پس هر لیست دارای [tex]a=\frac{N}{K}[/tex] عضو هست، پس کل داده‌ها در K لیست قرار گرفته‌اند (لیست اول از اندیس ۱ شروع میشه، دومی از اندیس ۲، سومی از ۳ و ... آخری از K. عنصر بعدی که عنصر K+1 ام هست توو همون لیست اول می‌افته که بالا نشون دادیم. پس همون K تا لیست داریم).
مرتبه‌ی زمانی مرتب کردن و یا در واقع ادغام K لیست مرتب شده که روی هم (سر جمع) N تا عضو دارند [tex]O(NlogK)[/tex] هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۴ آبان ۱۳۹۵ ۰۴:۲۱ ب.ظ)Behnam نوشته شده توسط:واقعا خیلی ممنون بابت پاسخ(04 آبان ۱۳۹۵ ۱۲:۳۰ ب.ظ)mostafaheydar1370 نوشته شده توسط: سلام کسی می دونه این سوال چه جوری حل میشه ؟
فایل‌ها رو در خود مانشت آپلود کنید. روی پیوست تازه کلیک کنید، فایل رو انتخاب و آپلود کنید، در انتها روی گزینه‌ی اضافه کردن فایل پیوست به ارسال کلیک کنید. این لینکی که گذاشتید اصلاً باز نمیشه.
با توجه به فرض سؤال میشه نوشت [tex]A[1]<A[1+K][/tex]، همینطور میشه نوشت [tex]A[1+K]<A[1+2K][/tex] و ...، در نتیجه
[tex]A[1]<A[1+K]<A[1+2K]<A[1+3K]<...<A[1+aK][/tex]. در اینجا
[tex]1+aK\approx N \longrightarrow a=\frac{N}{K}[/tex]
پس لیست اول شامل عناصر ۱ و ۱+K و ۱+۲K و ... ۱+aK هست. یعنی a+1 تا عضو داره که [tex]a=\frac{N}{K}[/tex]. فرض می‌کنیم همون a تا عضو رو داره دقیقا (در حل مسأله تأثیری نداره). همین حالت رو برای اندیس‌هایی که از ۲ شروع بشن هم داریم و ...
پس هر لیست دارای [tex]a=\frac{N}{K}[/tex] عضو هست، پس کل داده‌ها در K لیست قرار گرفته‌اند (لیست اول از اندیس ۱ شروع میشه، دومی از اندیس ۲، سومی از ۳ و ... آخری از K. عنصر بعدی که عنصر K+1 ام هست توو همون لیست اول می‌افته که بالا نشون دادیم. پس همون K تا لیست داریم).
مرتبه‌ی زمانی مرتب کردن و یا در واقع ادغام K لیست مرتب شده که روی هم (سر جمع) N تا عضو دارند [tex]O(NlogK)[/tex] هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.