سلام. اگر پیچیدگی زمانی t(n) را از ما بخوان که محاسبه کنیم، طبق صورت برنامه چطور باید اینکار رو انجام بدیم؟
for (i=1;i<=n;i++)
{
j=n;
while (j>=1)
j=j/2;
}
ممنون میشم اگر یک توضیحی برای سوال بالا بدین و راه حلی بگید. با تشکر
(۰۳ آبان ۱۳۹۲ ۰۲:۳۴ ب.ظ)reza_a نوشته شده توسط: سلام. اگر پیچیدگی زمانی t(n) را از ما بخوان که محاسبه کنیم، طبق صورت برنامه چطور باید اینکار رو انجام بدیم؟سلام
for (i=1;i<=n;i++)
{
j=n;
while (j>=1)
j=j/2;
}
ممنون میشم اگر یک توضیحی برای سوال بالا بدین و راه حلی بگید. با تشکر
خوب حلقه داحلی منظورم همون while هست چون شمارندش داره هر دفعه تقسیم میشه به ۲ تعداد تکرارش میشود : [tex]log_2(n)[/tex]
حلقه بیرونی هم یه فور معمولی هست که ان بار اجرا میشود پس تعداد اجرا های این دو حلقه رو در هم ضرب میکنیم که میشود :
[tex]nlogn[/tex]
خیلی متشکرم. یعنی هر جا while داشت ۲ تا حساب میشه و حلقه for میشود n تا؟ بعد واحد محاسبه پیچیدگی زمانی log هست؟ ممنونم.
(۰۳ آبان ۱۳۹۲ ۰۷:۱۹ ب.ظ)reza_a نوشته شده توسط: خیلی متشکرم. یعنی هر جا while داشت ۲ تا حساب میشه و حلقه for میشود n تا؟ بعد واحد محاسبه پیچیدگی زمانی log هست؟ ممنونم.
اگر وقت و حوصله داری این id رو add کن تو یاهو مسنجر بیا یادت بدم.
nader.vojoudi
شما رو مفاهیم بنیادی پیچیدگی مشکل داری یکم.