پیچیدگی زمانی تابع زیر چقدر است؟

Question

این سوال مربوط به ساختمان داده است; زمان اجرای این برنامه چقدر است؟

int practice()
{
	int k =0 , i , n ;
	for(i=2 ; i<= n ; i+=2)
	{
		n=1;
		while(n>1)
		{
			k=k+1;
			n=n/2;
		}
	}
	return k;
}

Comments

کد صحیح هست، اگر با مبحث پیچیدگی زمان در ساختمان داده آشنایی داشته باشید شاید منظورم رو بهتر متوجه بشین
من خودم می دونم چطور اجرا میشه اما باید یک فرمول به دست بیارم مثلا
tn=c1+n*c2*c3
که به tn زمان اجرا میگن
حالا با توجه به کد من فکر میکنم جواب میشه
tn=c1+(n/2*c2)*c3

---

اولین باری که وارد حلقه میشوید، مقدار n را برابر 1 میکنید. علاوه بر اینکه while اجرا نمیشه، باعث میشه، شرط اجرای حلقه ی for هم نادرست شده و دیگه اجرا نشه. کلا یکبار حلقه اجرا میشه و برنامه تموم میشه

Answer 1

این درسته که حلقه while اجرا نمی شه ولی با این وجود پیچیدگی مقدار های متغییر ها و اجرا شدن حلقه for  را باید محاصبه کرد 

و به این ترتیب که :

1. سه متغییر محاسباتی دارید که می شود 3=1+1+1

2.برای اولین بار مقدار i برابر 2 است شرط حلقه برسی و چون n  برابر 1 است (در کل باید همون n  رو هم بیرون از جدول مقدار دهی کنه که نکرده و فکر کنم اگر توی یه کامپایلر ببرید خطلای نحوی رو بگیره)

3. وارد حلقه شده ولی چون شرط while بر قرار نیست از حلقه خارج و به i که مقدار آن 2 بوده 2 واحد دیگر اظافه می کند .

4. اکنون i  برابر 4 است و چون شرط حلقه for هم نقض می شود از حلقه for هم خارج و مقدار K را بر می گرداند 

درکل پیچیدگی حلقه for رو  n  می گیریم و جواب ما برابر است با 

T(n)=n+3