۰
subtitle
ارسال: #۱
محاسبه ی big-o در یک شبه کد
سلام دوستان.
من نمیدونم در محاسبه ی big-o در یک شبه کد باید چه قسمت هایی را در نظر بگیرم. و اصلا محاسبه ی big-o برای یک شبه کد چه مفهومی داره .
مثلا در کد زیر من فکر میکنم که big-o در اون[tex]4\times n\: \: 4[/tex] هست. ولی همه میگن اشتباهه.چرا؟ میشه یکی از دوستان توضیح بده؟
ممنون میشم اگه یه نفر راهنماییم کنه. مرسی
من نمیدونم در محاسبه ی big-o در یک شبه کد باید چه قسمت هایی را در نظر بگیرم. و اصلا محاسبه ی big-o برای یک شبه کد چه مفهومی داره .
مثلا در کد زیر من فکر میکنم که big-o در اون[tex]4\times n\: \: 4[/tex] هست. ولی همه میگن اشتباهه.چرا؟ میشه یکی از دوستان توضیح بده؟
int s=0;// 1 time
int h=1; // 1 time
int i=0; // 1 time
while(i<=n) // n+1 time
{
s++;// n time
h++; // n time
i++; // n time
}
int i=0; // 1 time
while(i<=n) // n+1 time
{
s++;// n time
h++; // n time
i++; // n time
}
۲
ارسال: #۲
RE: محاسبه ی big-o در یک شبه کد
سلام
ببین من میخوام یه مثال بزنم، بعد تعمیمش میدیم به این سوال.
فرض کن تو حساب بانکیت ۵۰،۰۰۰،۱۰۰ تومن پول داری، خب یکی ازت بپرسه چقدر تو حسابته چی میگی؟ نمیگی که ۵۰ میلیون و ۱۰۰ تومن پول دارم، میگی ۵۰ میلیون تو حسابمه (اگه یگی اونم
)
مرتبه زمانی هم دقیقا همینه، اگه الگوریتمت ۵۰،۰۰۰،۱۰۰ بار اجرا بشه، بخوای تو یه مقاله ای یا هرجایی تعداد اجراش رو بگی، نمیای بگی ۵۰ میلیون و ۱۰۰ بار، میگی ۵۰ میلیون بار.
خب با این مقدمه بیا فرض کنیم الگوریتمت n+100 بار اجرا میشه، اگه جای n بذاری ۵۰ میلیون، همون عبارت بالایی میشه، پس طبق آنچه گفته شد نیازی نیست بیای بگی الگوریتم من n+100 بار اجرا میشه.
*** البته اینکه n+100 بار اجرا میشه عدد دقیقه و مشکلی نیست. اما دقت کن:
فرض کن گاها الگوریتمت n+100 بار و گاها n+101 بار اجرا میشه، پس نیازی نیست اینا رو بگی، الگوریتم من n بار اجرا میشه کافیه.
----------------------
تو کد بالا:
داخل حلقه خودتم گفتی n بار اجرا میشه. حالا چندتا کد بیرون هست که بقولی یه اپسیلون بار اجرا میشن (۳ بار) و یکم هم داخل حلقه (۳n). اینا مسئله نیست. مهم اینه که الگوریتمت n بار اجرا میشه. (مرتبه اجراییش n هست طبق گفته های بالا)
مرتبه عم چند نوعه، تو بیگ اُ میای سقفشو در نظر میگیری، مثلا، میتونی بنویسی بیگ اوی n بار، خوب معلومه n بار اجرا میشه، میتونی بنویسی بیگ اوی n^2 بار، خب معلومه n بار اجرا میشه و n هم از n^2 کمتره.
البته تعریف ریاضی اینا تو کتابا هست که من نخواستم باز نویسی کنم.
اینم یه تعریف از ویکی پدیا:
ببین من میخوام یه مثال بزنم، بعد تعمیمش میدیم به این سوال.
فرض کن تو حساب بانکیت ۵۰،۰۰۰،۱۰۰ تومن پول داری، خب یکی ازت بپرسه چقدر تو حسابته چی میگی؟ نمیگی که ۵۰ میلیون و ۱۰۰ تومن پول دارم، میگی ۵۰ میلیون تو حسابمه (اگه یگی اونم
)مرتبه زمانی هم دقیقا همینه، اگه الگوریتمت ۵۰،۰۰۰،۱۰۰ بار اجرا بشه، بخوای تو یه مقاله ای یا هرجایی تعداد اجراش رو بگی، نمیای بگی ۵۰ میلیون و ۱۰۰ بار، میگی ۵۰ میلیون بار.
خب با این مقدمه بیا فرض کنیم الگوریتمت n+100 بار اجرا میشه، اگه جای n بذاری ۵۰ میلیون، همون عبارت بالایی میشه، پس طبق آنچه گفته شد نیازی نیست بیای بگی الگوریتم من n+100 بار اجرا میشه.
*** البته اینکه n+100 بار اجرا میشه عدد دقیقه و مشکلی نیست. اما دقت کن:
فرض کن گاها الگوریتمت n+100 بار و گاها n+101 بار اجرا میشه، پس نیازی نیست اینا رو بگی، الگوریتم من n بار اجرا میشه کافیه.
----------------------
تو کد بالا:
داخل حلقه خودتم گفتی n بار اجرا میشه. حالا چندتا کد بیرون هست که بقولی یه اپسیلون بار اجرا میشن (۳ بار) و یکم هم داخل حلقه (۳n). اینا مسئله نیست. مهم اینه که الگوریتمت n بار اجرا میشه. (مرتبه اجراییش n هست طبق گفته های بالا)
مرتبه عم چند نوعه، تو بیگ اُ میای سقفشو در نظر میگیری، مثلا، میتونی بنویسی بیگ اوی n بار، خوب معلومه n بار اجرا میشه، میتونی بنویسی بیگ اوی n^2 بار، خب معلومه n بار اجرا میشه و n هم از n^2 کمتره.
البته تعریف ریاضی اینا تو کتابا هست که من نخواستم باز نویسی کنم.
اینم یه تعریف از ویکی پدیا:
Example of Big O notation: f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g., x0 = 5) such that f(x) <= cg(x) whenever x > x0.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close