پیچیدگی زمتنی merge sort

[sahar-63]

چگونه می شود در merge sort ثابت کرد پیچیدگی زمانی حالتی که آرایه را به سه قسمت تقسیم می کنیم با حالتی که آن را به دو قسمت تقسیم می کنیم برابر است؟

[404_3140]

hamoon tor ke midoonid farghi nadare payeye logarithm chi bashe. chon faghat dar yek zaribe sabet zarb mishe:
masalan logn=log2*lgn
(lg yani logarithm dar payeye 2)
1.ye rah ba estefade az ghazieye master hast:
f(n) =3f(n/3)+O(n) => f az O(nlgn) e
2. derakhte bazgasht ro bekeshid o sabet konid O(nlgn) e
3. esteghra!

[kiani_behzad]

راه سوم هم با استفاده هز حل رابطه ی بازگشتیش هست که در هر دو حالت به یک نتیجه می رسید و همونطور که دوستمون گفتن ضرایب ثابت مهم نیست