۰
subtitle
سلام.
سوال اولتون:
trace می کنیم:
z=0
i=1
z++ ……. j=1
z++ ……. j=2
z++ ……. j=4
.
.
z++ ……. j=n
که j هر بار در ۲ ضرب میشه، پس logn بار zزیاد میشه. اصلاح شد. اشتباه نوشته بودم
i=2
z++ …... j=1
z++ …... j=2
z++ ……. j=4
.
.
z++ …….. j=n
که j هر بار در ۲ ضرب میشه، پس logn بار zزیاد میشه.
.
.
و به همین ترتیب تا i به n برسه. پس به ازای i از ۱تا n حلقه ی داخلی هر بار logn بار اجرا میشه و هر بار logn تا به zافزوده میشه. پس مقدار نهایی zمیشه nlogn و مرتبه ی این کد هم همین هست.
سوال دوم:
i=1
k=1 … j=1 … z++ … j+=2
z++ … j+=2
z++ … j+=2
.
.
چون گام j ۲ هست، پس این حلقه ی داخلی n/2 بار اجرا میشه تا برسه j برسه به n/2
تا اینجا z هم n/2 بار افزایش داشته.
حالا واسه k=2, k=3 تا k=l دقیقا همین رو داریم، یعنی l*n/2
اینا واسه i=1 بود. واسه i=2 تا i=n کل داستان بالا برقرار هست و درنتیجه z و هم مرتبه ی تابع میشه : l*n*n/2
سوال اولتون:
trace می کنیم:
z=0
i=1
z++ ……. j=1
z++ ……. j=2
z++ ……. j=4
.
.
z++ ……. j=n
که j هر بار در ۲ ضرب میشه، پس logn بار zزیاد میشه. اصلاح شد. اشتباه نوشته بودم
i=2
z++ …... j=1
z++ …... j=2
z++ ……. j=4
.
.
z++ …….. j=n
که j هر بار در ۲ ضرب میشه، پس logn بار zزیاد میشه.
.
.
و به همین ترتیب تا i به n برسه. پس به ازای i از ۱تا n حلقه ی داخلی هر بار logn بار اجرا میشه و هر بار logn تا به zافزوده میشه. پس مقدار نهایی zمیشه nlogn و مرتبه ی این کد هم همین هست.
سوال دوم:
i=1
k=1 … j=1 … z++ … j+=2
z++ … j+=2
z++ … j+=2
.
.
چون گام j ۲ هست، پس این حلقه ی داخلی n/2 بار اجرا میشه تا برسه j برسه به n/2
تا اینجا z هم n/2 بار افزایش داشته.
حالا واسه k=2, k=3 تا k=l دقیقا همین رو داریم، یعنی l*n/2
اینا واسه i=1 بود. واسه i=2 تا i=n کل داستان بالا برقرار هست و درنتیجه z و هم مرتبه ی تابع میشه : l*n*n/2
