بدست آوردن اوی بزرگ O الگوریتم

Question

مفهموم این O الگوریتم که می گن چیه ؟  بعد جه جوری محاسبه میشه ؟

با تشکر .

Answer 1

(صرفا جهت اطلاع)

تعریف ریاضی تابع O که در کتاب طراحی الگوریتم با رویکرد خلاقانه نوشته ی یودی منبر آمده است:

برای ارزیابی زمان اجرای یک الگوریتم، از عوامل ثابت چشم پوشی میکنیم. برای بهتر انجام دادن این کار به نماد گذاری ویژه ای احتیاج داریم. میگوییم تابع ( g( n از ( ( O ( f (n است اگر ثابت های c و N وجود داشته باشند به گونه ای که برای n>=N داشته باشیم:

g(n) <= c.f(n)

به عبارت دیگر به ازای n های به اندازه ی کافی بزرگ، تابع( g( n از چند برابر تابع( f( n بیشتر نیست. (در این جا "چند" ضریبی ثابت است)

تبصره: ممکن است برای n های کوچک، (  g( n از (  c.f( n خیلی کوچکتر باشد ولی نماد O، آن را تنها از بالا محدود میکند.

مثلا 5n^2 + 15 از ( O( n^2 است.

Answer 2

O به معنای order هست یعنی تعداد عملیاتی که الگوریتم نیاز داره تا اجرا بشه مثلا برای پیدا کردن بزرگترین عضو یه ارایه با n عضو میگن (O(n چون توی بدتیرن حالت باید همه عضای ارایه رو چک کنیم پس با n عملیات نیاز داریم

محاسبه هم روش خاصی نداره مثل همین مثالی که زدم محاسبه میکنن ولی مثلا ضریب رو توی order حساب نمیکنن  یعنی (O(n) = O (2n  و یا قواعد دیگه که من زیاد اشنا نیستم

Answer 3

اگر بخواهیم رفتار یک الگوریتم را برای ورودی های بزرگ بررسی کنیم از نماد های مجانبی مانند تتا ، امگا ، بیگ ا و دیگر موارد استفاده می کنیم - O یک الگوریتم به این معناست که رفتار آن الگوریتم در بدترین حالت از آن حد تجاوز نخواهد کرد (اگر از ثابت ها صرف نظر کنیم )