19 فروردین 1391, 01:49 ب.ظ
24 فروردین 1391, 11:15 ب.ظ
یه روش راحت برای حل این مسله بصورت سر انگشتی اینه:
عناصر مرتب شده یعنی اینکه عناصر بترتیب سر جاشون هستن . به تعبیری شما باید بدونید که هر عنصری از عناصر قبلی اش بزرگتر و از عناصر قبلیش کوچکتره از اونجایی که تعداد عناصر n هستش پس شما n تا پیمایش داری برای هر عنصر , و برای اینکه بدونی هر عنصر در سر جای درستش هست میشه از یک الگوریتم مثله جستجوی دودیی که از مرتبه log n هستش استفاده کرد که در کمترین حالت همون nlgn میشه . ولی در حالت کلی به این اثبات نمی گین ولی کمک می کنه بفهمی چرا کمتر از nlgn نمیشه .
عناصر مرتب شده یعنی اینکه عناصر بترتیب سر جاشون هستن . به تعبیری شما باید بدونید که هر عنصری از عناصر قبلی اش بزرگتر و از عناصر قبلیش کوچکتره از اونجایی که تعداد عناصر n هستش پس شما n تا پیمایش داری برای هر عنصر , و برای اینکه بدونی هر عنصر در سر جای درستش هست میشه از یک الگوریتم مثله جستجوی دودیی که از مرتبه log n هستش استفاده کرد که در کمترین حالت همون nlgn میشه . ولی در حالت کلی به این اثبات نمی گین ولی کمک می کنه بفهمی چرا کمتر از nlgn نمیشه .
03 آبان 1391, 12:23 ق.ظ
اینم اثباتش :