Meta tags:
description=طراحی الگوریتم این وبلاگ به منظور ارتقای دانش الگوریتم طراحی شده است.;

Headings (most frequently used words):

الگوریتم, مرتب, سازی, sort, یا, طراحی, به, heap, merge, های, فلوید, دایجسترا, این, وبلاگ, منظور, ارتقای, دانش, شده, است, درجی, insertion, انتخابی, selection, quick, کدام, بهتره, حبابی, bubble, از, تفاوت, دیکسترا, کوتاهترین, مسیر, روش, توده, ای, کپه, با, ادغام, نوشته, پیشین, پیوندها,

Text of the page (most frequently used words):
این (65), #الگوریتم (56), است (47), مرتب (47), زمانی (39), داده (38), سازی (37), مقایسه (35), های (33), مرتبه (32), درخت (31), قرار (31), شده (30), sort (26), heap (26), برای (25), گره (25), آرایه (24), کنیم (22), صورت (21), حالت (20), عدد (19), for (19), شود (18), انجام (17), بررسی (16), int (16), تعداد (15), ادغام (14), بدترین (14), حلقه (14), دهیم (13), اگر (12), باشد (12), مقدار (12), فلوید (12), array (12), ۱۳۹۲ (11), نوشته (11), کار (11), دارد (10), بسته (10), ساعت (9), توسط (9), فریبا (9), nlogn (9), بهترین (9), دهد (9), بار (9), تیر (8), باید (8), نسبت (8), بین (8), توجه (8), نیاز (8), یکی (8), کنید (8), کرده (8), ریشه (8), یال (8), خانه (7), کوچکتر (7), درجی (7), merge (7), دیگر (7), نود (7), سپس (7), خود (7), نمی (7), اعداد (7), min (7), وزن (7), گراف (7), temp (7), حبابی (7), همه (6), مورد (6), نیز (6), تقسیم (6), مسئله (6), قسمت (6), هایی (6), logn (6), داریم (6), جدید (6), عمل (6), حال (6), گرفته (6), واسط (6), گیرد (6), درست (6), کند (6), arr (6), برابر (5), چرا (5), زیر (5), شوند (5), نتیجاً (5), یعنی (5), گیرند (5), کارت (5), swap (5), دارند (5), شنبه (5), جای (5), مسیر (5), عنوان (5), شمارنده (5), دایجسترا (5), bubble (5), جابه (5), quick (5), index_of_min (5), وبلاگ (4), طراحی (4), بیست (4), بدست (4), اضافه (4), کرد (4), اما (4), زیاد (4), insertion (4), حافظه (4), ایندکس (4), آخر (4), بالا (4), پایین (4), کوچک (4), بزرگ (4), آنقدر (4), مجموعه (4), اولین (4), موجود (4), واحد (4), max (4), بزرگترین (4), آخرین (4), سایر (4), سمت (4), پیمایش (4), کوتاهترین (4), جفت (4), وجود (4), مبداء (4), تعیین (4), صورتی (4), استفاده (4), کارایی (4), flag (4), کدام (4), جایی (4), pointer (4), مرز (4), نامرتب (4), کامپیوتر (3), خرداد (3), ایجاد (3), تغییر (3), ذخیره (3), سطح (3), همان (3), فرض (3), ترتیب (3), مثال (3), ابتدا (3), بگیرد (3), and (3), هشتم (3), heapsort (3), برمی (3), جایگزین (3), ترین (3), واقع (3), توده (3), پیدا (3), آوردن (3), ولی (3), end (3), swaps (3), ابتدای (3), pivot (3), سریع (3), mergesort (3), بعدی (3), selection (3), انتخابی (3), دانلود (2), پروژه (2), هست (2), شما (2), بگذارید (2), دوشنبه (2), هفتم (2), بازگشتی (2), آمده (2), فرمول (2), جمع (2), داشته (2), بسیار (2), خوبی (2), ادغامی (2), سرعت (2), رشد (2), کمکی (2), میانگین (2), result (2), وقتی (2), ارتفاع (2), لگاریتم (2), نودها (2), رسیده (2), بدون (2), طور (2), شکل (2), توان (2), نمایش (2), دارید (2), شروع (2), غلبه (2), گردد (2), مسلماً (2), دوباره (2), ریزد (2), سری (2), آرایش (2), نحوه (2), آسان (2), ساختمان (2), یافتن (2), برداشته (2), فرزندانش (2), بزرگتر (2), کپه (2), تودرتو (2), خاطر (2), همین (2), مشخص (2), مینیمم (2), مقصد (2), تشکیل (2), بیرونی (2), درونی (2), مشابه (2), منفی (2), بیشتری (2), مثلا (2), دیکسترا (2), باز (2), فقط (2), بیشتر (2), بیهوده (2), طرفی (2), باعث (2), نکنیم (2), بهتر (2), تفاوت (2), break (2), void (2), نیست (2), false (2), modified (2), ساده (2), اول (2), پیش (2), ارجحیت (2), رفته (2), compares (2), رود (2), نشده (2), جلو (2), بریم (2), blogfa, com, لینوکس, ویندوز, چیز, اینترنت, رایگان, خاص, پیوندها, پیشین, عناوین, آرشیو, پروفایل, مدیر, سایت, ایرانی, ندرت, بحث, قراره, مختلف, نقد, نظری, موضوع, لطفا, اطلاعاتتون, اشتراک, تابع, لگوریتم, زیرمسئله, بوجود, مسائل, هاست, محاسبه, طریق, nlognکندتر, کاهش, کاراتر, بوده, بالاتری, عکس, کمتر, علاوه, دخیره, متوسط, حالتnlogn, طولn, nباشد, طول, باشند, بعد, معلوم, داد, combine, اید, طوری, هرکدام, بود, تمام, چیدمانشان, باهم, ترتیبی, آرا, جداگانه, نمونه, divide, conquer, کمتری, علت, اساس, zip, مبنای, درخت1, log, nنود, گفت, حدس, دادن, قرارگیری, نشان, صفرم, خالی, رابطه, نخورد, داراست, فرزند, راست, ایندکس2i, و2i, پیاده, بارها, راحتر, همچون, لینک, لیست, بیشترین, کمترین, خورده, روز, برداشتن, بگیرند, گونه, خارج, مساوست, مساویست, دودویی, تقریباً, کامل, وmin, نوع, درختheap, آشنا, شویم, جمعه, قبل, نقطه, نود2, نود5, برویم, درون, زیادی, کوتاه, مسطح, دار, شرح, روش, پریم, پوشای, بایست, نظیر, بلمن, فورد, اگرچه, شماره, مرتبط, گرهv, تکرار, داری, ندارند, تاکید, کنم, یکسانی, کشیده, خودش, چون, یالی, loop, مصرف, چند, دستور, نتوان, چشم, پوشی, ندارد, کاراترست, مبدا, پنجشنبه, سیزدهم, function, outer, bubblesort2, پایان, یافته, انتهای, معناست, بودن, نشود, true, نسخه, کمی, معکوس, اند, حداکثر, ایست, بقیه, انتخاب, برد, ترم, بچه, یاد, کنار, ادامه, یابد, انتها, دوتا, دوم, هستند, unstable, stable, بیاید, امکان, minimum, maximum, درستی, خواهند, داشت, quicksort, خواهیم, اضافی, place, درجا, تقریبا, شبیه, دیگری, تفاوتی, بهتره, پنجم, تره, کوچولو, مفهوم, هربار, کوچکترین, اینکه, اوقات, بهتری, کلاس, انواع, یکم, عملیات, انتساب, چندتا, insertion_sort, الگوریتمشه, انکه, بزرگترند, مکان, 2مقایسه, عددی, همانطور, دیدید, مرحله, الزاما, الان, تنها, نظر, رفت, مراحل, یشتر, مرتبی, خواهد, لیستی, منظور, ارتقای, دانش,

Text of the page (random words):
طراحی الگوریتم طراحی الگوریتم این وبلاگ به منظور ارتقای دانش الگوریتم طراحی شده است مرتب سازی درجی insertion sort مرتب سازی درجی insertion sort 1 ابتدا ما لیستی از داده های نامرتب را به کامپیوتر داده و آن ها را در یک آرایه ذخیره می کنیم 7 8 5 2 4 6 3 2 در این الگوریتم باید مرز بین داده های مرتب شده و نامرتب را تعیین کرد سپس هر بار داده ی نامرتب با داده ی مرتبی که در مرز بین دو قسمت قرار گرفته مقایسه می شود و در صورت نیاز جابه جا خواهد شد 7 8 5 2 4 6 3 3 در این مثال اولین عدد نامرتب 8 است آن را با عدد سمت چپ مقایسه می کنیم و در صورت نیاز عمل swap را انجام می دهیم سپس pointer مرز را یک خانه جلو می بریم توجه کنید که در این قسمت عدد 8 تنها با یک مقایسه به خانه مورد نظر رفت اما در مراحل بعدی تعداد مقایسه ها یشتر می شود 7 8 5 2 4 6 3 حال اولین عدد مرتب نشده 5 است که با دو مقایسه به جای درست خود می رود 7 5 8 2 4 6 3 5 7 8 2 4 6 3 الان عدد 5 در جای درست خود قرار گرفته پس pointer را یک واحد جلو می بریم همانطور که دیدید در این مرحله دو مقایسه و دو جابه جایی انجام شد پس الزاما عدد مرتب نشده فقط با یک عدد که در سمت چپ pointer هست مقایسه نمی شود 5 7 8 2 4 6 3 2 5 7 8 4 6 3 4 حال عددی که مورد بررسی قرار می گیرد 4 است 4 کوچکتر از 7 و 8و 5 است ولی از 2 کوچکتر نیست در این صورت 4 مقایسه انجام شده و 3 جابه جایی صورت می گیرد باز هم مرز pointer یک واحد اضافه می کنیم 2 4 5 7 8 6 3 5 در این قسمت عدد 6 با 3 مقایسه و 2 جابه جایی در مکان درست خود قرار گرفته و با 4 و 2مقایسه نمی شود 2 4 5 6 7 8 3 6 در آخر عدد 3 برای انکه در جای درست خود قرار بگیرد تا جایی که اعداد از آن بزرگترند پیش رفته و عمل مقایسه را انجام می دهد 2 3 4 5 6 7 8 بررسی مرتبه ی زمانی این کد الگوریتمشه void insertion_sort int arr int n int i j t for i 1 i n i t arr i for j i j 0 j if t arr j 1 break arr j arr j 1 arr j t برای بدست آوردن مرتبه زمانی باید بررسی کنیم که تو هر حلقه چندتا مقایسه انجام می شود در بدترین حالت به همان تعداد i این حلقه انجام می شود یعنی عدد مورد بررسی به ابتدای آرایه می رود a 1 2 3 4 and t 0 4 compares a 1 2 3 i and t 0 i compares نتیجاً تعداد عملیات انتساب که هر کدام مرتبه ی زمانی o 1 را دارند برابر است با for int i 1 i for j i 1 j 0 t a j 1 a j جمع تعداد مقایسه ها 1 2 3 n 1 n 1 n 2 پس مرتبه زمانی آن برابر است با o n 2 نوشته شده در دوشنبه سی و یکم تیر ۱۳۹۲ ساعت 19 5 توسط فریبا مرتب سازی انتخابی selection sort مرتب سازی انتخابی و درجی selection sort insertion sort این دو مرتب سازی بیشتر اوقات کارایی بهتری نسبت به مرتب سازی حبابی دارند اگر چه این دو مرتب سازی در یک کلاس از انواع الگوریتم قرار نمی گیرند مرتب سازی انتخابی selection sort این مرتب سازی مفهوم ساده ای نسبت به سایر مرتب سازی ها دارد این الگوریتم هربار کوچکترین مقدار یا بزرگترین مقدار را برداشته بسته به اینکه اعداد را از بزرگ به کوچک یا از کوچک به بزرگ مرتب می کنید و در ابتدای آرایه قرار می دهد سپس عدد بزرگتر بعدی را پیدا می کند و این کار را تا زمانی که همه ی داده ها بررسی شوند انجام می دهد این مرتب سازی یه کوچولو از مرتب سازی حبابی bubble sort و modified bubble sort سریع تره for int x 0 x x int index_of_min x for int y x y y if array index_of_min array y index_of_min y int temp array x array x array index_of_min array index_of_min temp حلقه ی اول از 0 تا n رفته و حلقه ی بعدی از x تا n داده ها را پیمایش می کند مرتبه زمانی آن به طور میانگین o n n 2 است نوشته شده در سه شنبه بیست و پنجم تیر ۱۳۹۲ ساعت 19 48 توسط فریبا heap یا merge یا quick کدام بهتره heap sort بهتر است یا merge sort یا quick sort چه تفاوتی بین کارایی این الگوریتم ها وجود دارد مرتبه زمانی این مرتب سازی ها تقریبا شبیه به هم است پس کدام یک از آن ها نسبت به دیگری کارایی بیشتری دارد یکی از ارجحیت های heap sort و merge sort نسبت به quick sort مرتبه ی زمانی مرتب سازی سریع quick sort در بدترین حالت o n 2 است اما در دو الگوریتم دیگر o nlogn است از ارجحیت هایی که heapsort نسبت به mergesort دارد این است که این الگوریتم درجا in place است یعنی از حافظه ی اضافی استفاده نمی کند در mergesort ما نیاز به یک حافظه ی کمکی داریم تا داده ها را در آن ذخیره کنیم فرض کنید یک سری داده ی مشابه داریم که می خواهیم آن ها را مرتب کنیم اگر این داده ها را به heapsort دهیم مرتبه زمانی آن mergesort o n مرتبه زمانی o logn و مرتبه زمانی o n 2 quicksort را خواهند داشت از طرفی در مرتب سازی سریع از یک pivot استفاده می شود و دو قسمت ایجاد شده هر کدام به صورت بازگشتی مرتب می شوند که اگر pivot را به درستی تعیین نکنیم مثلا maximum pivot یا minimum باشد امکان دارد بدترین حالت در مرتبه زمانی یعنی o n 2 پیش بیاید merge sort یک الگوریتم stable است در صورتی که quick و unstable heap هستند نوشته شده در شنبه بیست و دوم تیر ۱۳۹۲ ساعت 11 30 توسط فریبا مرتب سازی حبابی bubble sort مرتب سازی حبابی bubble sort یکی از ساده ترین مرتب سازی هایی که ترم اول به بچه های کامپیوتر یاد می دن مرتب سازی حبابی است در این الگوریتم از ابتدای آرایه شروع کرده و هر دو جفت عدد کنار هم با هم مقایسه شده و در صورت نیاز جابه جا می شوند و این کار تا آخر ادامه می یابد در واقع هر بار بزرگترین مقدار را از بین داده ها پیدا کرده و در انتها قرار می دهیم این مرتب سازی از دوتا حلقه ی for تشکیل شده حلقه ی بیرونی شمارنده ای است که هر بار یک عدد را برای مقایسه با بقیه ی اعداد انتخاب کرده و بزرگترین را به جای درست خود می برد حلقه ی for درونی نیز شمارنده ایست که عمل مقایسه عدد با سایر اعداد را انجام می دهد for int x 0 x for int y 0 y if array y array y 1 int temp array y 1 array y 1 array y array y temp در بدترین حالت یعنی زمانی که اعداد به صورت معکوس در آرایه قرار گرفته اند حداکثر n مقایسه صورت می گیرد مرتبه زمانی این الگوریتم در بهترین حالت و بدترین حالت o n 2 مرتب سازی حبابی با کمی تغییر modified bubble sort بهترین نسخه ی الگوریتم مرتب سازی حبابی یک flag دارد این flag در صورتی که عمل swap بین جفت عدد انجام شود true شده و در صورتی که swap انجام نشود flag false می شود false بودن flag به این معناست که عمل sort پایان یافته و دیگر نیاز نیست تا انتهای آرایه داده ها را پیمایش کنیم در این صورت در بهترین حالت مرتبه ی زمانی الگوریتم o n می شود void bubblesort2 int a int n int temp swap for int i 0 i 2 i swaps 0 for int j 0 j 1 j if a j a j 1 temp a j a j a j 1 a j 1 temp swaps if swaps 0 break end of if end of outer for end of function نوشته شده در پنجشنبه سیزدهم تیر ۱۳۹۲ ساعت 17 35 توسط فریبا از تفاوت های الگوریتم فلوید و دایجسترا از تفاوت های الگوریتم فلوید و دایجسترا در الگوریتم dj یک گره با سایر گره ها مقایسه می شود ولی در الگوریتم فلوید هر بار یک گره مبدا می شود اگر تعداد گره ها زیاد باشد الگوریتم فلوید کاراترست اما اگر تعداد گره ها کم است الگوریتم dj بهتر کار می کند وجود چند دستور با مرتبه زمانی o 1 در الگوریتم dj باعث شده که در حالت گره های زیاد نتوان از آن ها چشم پوشی کرد نتیجاً برای گراف هایی با گره های زیاد این الگوریتم کارایی خوبی ندارد از طرفی در الگوریتم فلوید چون در حلقه های for یالی که از یک گره به خود برمی گردد loop را هم بررسی می کنیم زمانی را بیهوده مصرف کرده و همین باعث شده که برای گراف هایی با یال های کم از الگوریتم فلوید استفاده نکنیم توجه کنید که در یک گراف با n گره در الگوریتم فلوید n مقایسه بیهوده مقایسه یال کشیده شده از یک گره به خودش با مرتبه ی زمانی o 1 صورت می گیرد دو الگوریتم مرتبه زمانی یکسانی دارند ولی سرعت الگوریتم فلوید بیشتر است باز هم تاکید می کنم اگر مرتبه زمانی الگوریتم فلوید o n 3 است فقط به خاطر این است که برای هر جفت گره کوتاهترین مسیر مشخص می شود نوشته شده در شنبه هشتم تیر ۱۳۹۲ ساعت 19 45 توسط فریبا الگوریتم دایجسترا یا دیکسترا الگوریتم دایجسترا یا دیکسترا این الگوریتم هم یکی از الگوریتم های پیمایش گراف است که مسئله ی کوتاهترین مسیر از مبداء واحد را برای گراف های وزن داری که یال با وزن منفی ندارند را حل می کند در این الگوریتم یک گره مثلا گره شماره ی یک به عنوان مبداء تعیین شده سپس این گره با همه ی یال های i مقایسه شده و وزن یال مرتبط با گره یک در d i قرار می گیرد سپس برای هر گرهv حلقه ی for تکرار می شود d w min d w d v l v w این الگوریتم مشابه الگوریتم پریم برای بدست آوردن درخت پوشای مینیمم می باشد در صورتی که گراف یال با وزن منفی داشته باشد این الگوریتم درست کار نمی کند و می بایست از الگوریتم های دیگر نظیر بلمن فورد اگرچه مرتبه ی زمانی بیشتری دارند استفاده کرد مرتبه زمانی o n 2 نوشته شده در شنبه هشتم تیر ۱۳۹۲ ساعت 19 44 توسط فریبا الگوریتم کوتاهترین مسیر به روش فلوید الگوریتم های زیادی برای بدست آوردن کوتاه ترین مسیر در یک گراف مسطح و وزن دار وجود دارد که ما دو الگوریتم فلوید و دایجسترا را شرح می دهیم الگوریتم فلوید در این الگوریتم هر بار یک گره به عنوان مبداء یک گره به عنوان واسط و یک گره به عنوان مقصد تعیین می شود این الگوریتم از سه حلقه ی for تودرتو تشکیل شده حلقه ی for بیرونی شمارنده ای برای گره ی واسط است حلقه ی for درون آن شمارنده ای برای گره مبداء و حلقه ی درونی آن نیز شمارنده ای برای گره مقصد است برای مثال اگر قرار است از از نود 3 با واسط نود2 به نود5 برویم مینیمم وزن یال های 2 5 3 2 و 3 5 به عنوان وزن یال 3 5 قرار می گیرد c i j min c i j c i k c k j حال اگر قرار باشد نقطه 3 6 با واسط 5 را بررسی کنیم c 3 6 min c 3 6 c 3 5 c 5 6 در این صورت مقدار c 5 3 از قبل مشخص شده حال چه با واسط چه بی واسط بررسی مرتبه زمانی الگوریتم توجه کنید که در این الگوریتم ما کوتاهترین مسیر بین همه جفت گره ها را پیدا می کنیم در واقع وجود سه حلقه ی for تودرتو به خاطر همین است o n 3 نوشته شده در جمعه هفتم تیر ۱۳۹۲ ساعت 19 18 توسط فریبا مرتب سازی توده ای یا کپه heap sort مرتب سازی توده ای یا کپه heap sort برای بررسی این نوع از مرتب سازی ابتدا باید با درختheap آشنا شویم درخت heap یک درخت دودویی تقریباً کامل است درخت max heap وmin heap درخت max heap در این درخت هر نود یا گره از فرزندانش بزرگتر یا مساویست درخت min heap در این درخت هر نود یا گره از فرزندانش کوچکتر یا مساوست در مرتب سازی توده ای داده ها را در یک درخت heap min قرار داده هر بار مقدار موجود در ریشه ی درخت را برداشته و آخرین گره قرار داده شده در درخت را جایگزین آن می کنیم با این کار آرایش درخت heap به هم خورده و باید دوباره درخت heap را به روز کنیم این کار را برداشتن اعداد آنقدر انجام می دهیم تا همه ی داده ها یکی یکی به جای ریشه قرار بگیرند این گونه داده ها از بزرگ به کوچک از درخت heap خارج شده و در یک حافظه قرار می گیرند توجه در درخت heap max یافتن بیشترین مقدار و در درخت min heap یافتن کمترین مقدار بسیار آسان است برای پیاده سازی درخت heap آرایه بهترین ساختمان داده است چرا که در درخت heap شما نیاز دارید که بارها درخت را بالا به پایین یا پایین به بالا پیمایش کنید نتیجاً در آرایه این کار راحتر از ساختمان داده ای همچون لینک لیست است در این صورت داده ها به ترتیب در آرایه قرار می گیرند مسلماً اولین خانه ی آرایه مقدار ریشه را داراست فرزند سمت چپ و سمت راست به ترتیب در خانه هایی با ایندکس2i و2i 1 قرار می گیرند خانه ی صفرم آرایه را خالی بگذارید تا رابطه ی بین ایندکس ها به هم نخورد در این صورت ایجاد درخت heap آسان می شود توجه شکل بالا یک درخت heap min است که نحوه ی قرارگیری داده ها در آرایه را نشان می دهد نحوه ی مرتب سازی را نمایش نمی دهد بررسی مرتبه ی زمانی این الگوریتم در بهترین و بدترین حالت باید گفت که در این الگوریتم نمی توان بهترین یا بدترین حالت را حدس زد چرا که در درخت heap هر بار که مقدار موجود در ریشه را برمی داریم و مقدار آخرین نود را جایگزین آن می کنیم درخت heap به هم می ریزد در واقع اگر یک سری از داده های مرتب را در یک درخت heap قرار دهیم هر بار با قرار دادن آخرین نود در ریشه آرایش اعداد به هم می ریزد بررسی مرتبه زمانی فرض کنید یک درخت max heap داریم مسلماً بزرگترین عدد در ریشه قرار گرفته آن عدد را برمی داریم و آخرین نود را جایگزین آن می کنیم حال باید دوباره درخت خود را heap کنیم بدترین حالت زمانی رخ می دهد که طی مقایسه ی عدد قرار گرفته در ریشه با سایر نودها عدد ریشه در پایین ترین سطح درخت قرار بگیرد پس اگر ارتفاع درخت1 log n 1 باشد تعداد مقایسه های انجام شده logn است نتیجاً برای nنود تعداد کل مقایسه ها nlogn است توجه مبنای لگاریتم دو است مرتبه ی زمانی θ nlogn heapsort zip دانلود نوشته شده در سه شنبه بیست و هشتم خرداد ۱۳۹۲ ساعت 18 15 توسط فریبا مرتب سازی با ادغام merge sort مرتب سازی با ادغام merge sort مرتب سازی با ادغام یک نمونه از الگوریتم های تقسیم و غلبه divide and conquer است مرتبه ی زمانی این الگوریتم در بدترین حالت نسبت به الگوریتم مرتب سازی درجی رشد کمتری دارد و علت آن به اساس الگوریتم که تقسیم و غلبه است بر می گردد ابتدا داده ها را به دو قسمت تقسیم می کنیم سپس برای هر مجموعه از داده ها این کار را انجام می دهیم این کار را آنقدر انجام می دهیم تا هر داده در یک مجموعه ی جداگانه قرار بگیرد سپس مجموعه ها دو تا دو تا با هم مقایسه کرده و در صورت نیاز عمل swap را انجام می دهیم حال برای ادغام مجموعه ها آرایه های کوچکتر از اولین ایندکس آرایه ها شروع کرده و داده ها را باهم مقایسه می کنیم برای مثال مقدار موجود در خانه های هر یک از آرایه ها را با هم مقایسه کرده و مقدار کوچکتر را در آرایه ی جدید قرار می داده و ایندکس آن را یک واحد اضافه می کنیم این کار را آنقدر انجام می دهیم تا زمانی که یکی از آرایه ها به آخر رسیده باشد در این صورت داده های موجود در آرایه ی دیگر را به همان ترتیبی که قرار دارند در آرا یه ی جدید قرار دهیم ادغام combine فرض کنید دو بسته کارت مرتب شده دارید که این بسته ها از بالا به پایین به ترتیب از کوچک به بزرگ قرار داده اید در این صورت برای ادغام این بسته کارت ها به طوری که بسته ی جدید هم مرتب باشد باید هر بار کارت های دو بسته را با هم مقایسه کرده و هرکدام کوچکتر بود را در بسته ی جدید قرار دهیم این کار را آنقدر انجام می دهیم تا یکی از بسته ها تمام شود در این صورت کارت های بسته ی دیگر را بدون تغییر چیدمانشان به بسته ی کارت جدید اضافه می کنیم بررسی مرتبه ی زمانی در بهترین حالت همان طور که از شکل معلوم است می توان داده ها را با درخت نمایش داد بهترین حالت زمانی رخ می دهد که وقتی دو آرایه به طول n 2 را با هم ادغام می کنیم تعداد مقایسه ها n 2 باشد یعنی داده ها مرتب باشند در این صورت است که بعد از n 2 مقایسه ایندکس یکی از آرایه ها به آخر رسیده و n 2 داده ی دیگر بدون مقایسه در آرایه ی جدید قرار می گیرند پس تعداد مقایسه ها در هر سطح درخت به صورت زیر می باشد t n n 2 n 4 n 8 nlogn 1 2 1 4 1 8 n 2 logn result nlogn توجه ارتفاع درخت برابر است با لگاریتم تعداد نودها logn نود مرتبه زمانی در بدترین حالت بدترین حالت زمانی رخ می دهد که وقتی دو آرایه به طولn 2 را با هم ادغام می کنیم تعداد مقایسه ها nباشد در این صورت تعداد مقایسه ها در هر سطح درخت به صورت زیر می باشد t n n n 2 n 4 nlogn 1 1 2 1 4 n logn result o nlogn نتیجاً مرتبه ی زمانی در حالت متوسط نیز برابر θ nlogn می باشد چرا که میانگین بهترین حالت و بدترین حالتnlogn می شود توجه در مرتب سازی با ادغام علاوه بر آرایه ای برای دخیره ی داده ها به یک آرایه ی دیگر برای ذخیره ی داده های مرتب شده نیاز داریم حافظه ی کمکی مقایسه ای بین الگوریتم مرتب سازی درجی insertion sort و ادغامی merge sort مرتب سازی درجی در بدترین حالت مرتبه ی زمانی n 2 را داشته که در مقایسه با مرتب سازی با ادغام با مرتبه زمانی o nlognکندتر است تغییر n به logn کاهش بسیار خوبی است اگر چه باید اضافه کرد که برای داده های کم الگوریتم درجی نسبت به ادغامی کاراتر بوده و سرعت بالاتری دارد اما برای داده های زیاد بر عکس است چرا که رشد nlogn نسبت به n 2 کمتر است محاسبه ی مرتبه زمانی الگوریتم با ادغام از طریق فرمول t n l t n b g n در این فرمول g n جمع مرتبه زمانی تقسیم داده ها و ادغام داده هاست b تعداد زیرمسئله های بوجود آمده از تقسیم مسئله به مسائل کوچکتر است و l نیز تعداد زیر مسئله هایی است که بررسی می شوند در مرتب سازی با ادغام b 2 و همه ی زیر مسئله های ایجاد شده بررسی می شوند g n نیز در این ا لگوریتم برابر n است چرا که تقسیم مسئله به دو قسمت مرتبه زمانی o 1 دارد و ادغام هر زیر مسئله نیز در بدترین حالت o n است پس تابع بازگشتی بدست آمده t n 2t n 2 n نوشته شده در دوشنبه بیست و هفتم خرداد ۱۳۹۲ ساعت 17 44 توسط فریبا تو سایت های ایرانی به ندرت در مورد طراحی الگوریتم بحث و بررسی شده تو این وبلاگ قراره الگوریتم های مختلف رو بررسی کنیم اگر نقد یا نظری در مورد این موضوع هست لطفا شما هم اطلاعاتتون رو به اشتراک بگذارید خانه پروفایل مدیر وبلاگ آرشیو وبلاگ عناوین نوشته ها نوشته های پیشین تیر ۱۳۹۲ خرداد ۱۳۹۲ پیوندها پروژه های خاص دانلود رایگان پروژه کامپیوتر و اینترنت همه چیز در مورد c لینوکس و ویندوز blogfa com