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

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

این کدی که نوشتید به دلیل اینکه قبل از ورود به حلقه while با مقدار اولیه n=1  مقدار دهی میشه اصلا حلقه while اش اجرا نمیشه!
من فکر میکنم باید این مقدار به n=i تغییر کنه چون در آن صورت حلقه while برای هر بار تکرار حلقه for حداقل یک بار اجرا میشه
یک بار دیگه از صحت کدتون مطمئن بشید و بگید که کدوم مد نظر تون هست تا جواب دقیق رو براتون بنویسم

---

کد صحیح هست، اگر با مبحث پیچیدگی زمان در ساختمان داده آشنایی داشته باشید شاید منظورم رو بهتر متوجه بشین
من خودم می دونم چطور اجرا میشه اما باید یک فرمول به دست بیارم مثلا
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