15 مهر 1391, 11:49 ق.ظ
15 مهر 1391, 12:09 ب.ظ
سلام. پیچیدگیش از مرتبه n میشه. فکر کنم کمتر از n بار دستور داخل حلقه درونی اجرا بشه. چون مقدار n همینجوری کم میشه و قبل از اینکه به صفر برسه از i کمتر میشه و از حلقه خارج میشه. تعداد دفعات اجراش میشه حدود n-lgn که از مرتبه n میشه.
19 مهر 1391, 09:20 ب.ظ
سلام
به ازای i=1 جمله x=x+1 ء n/2 بار اجرا میشود
به ازای i=1 جمله x=x+1 ء n/4 بار اجرا میشود
به همین ترتیب : تعداد اجرای دستور x=x+1 .....،=>ء(.........n/2+n/4+n/8) که اگر از n فکتور بگیریم عبارت زیر بدست می آید:
n*((1/2)/(1-(1/2))=(....1/2+1/4+1/8)n......که متبه اجرایی آن میشود( تتا n)
به ازای i=1 جمله x=x+1 ء n/2 بار اجرا میشود
به ازای i=1 جمله x=x+1 ء n/4 بار اجرا میشود
به همین ترتیب : تعداد اجرای دستور x=x+1 .....،=>ء(.........n/2+n/4+n/8) که اگر از n فکتور بگیریم عبارت زیر بدست می آید:
n*((1/2)/(1-(1/2))=(....1/2+1/4+1/8)n......که متبه اجرایی آن میشود( تتا n)