- امگا - تتا و... Ο ο، Ω ،θ،ω

[ffarzadd]

سلام توی طراحی الگوریتم - پیچیدگی زمانی رو قاطی کردم - جزوم مناسب نبوده - اگه امکانش هست به صورت قابل فهم نه کتابی بهم بگید اینا چطوری بدست میان مرسی

- امگا - تتا و... Ο ο، Ω ،θ،ω

دلیل این که موارد زیر بررسی شدن و درست یا نادرستند چیه؟ ممنون میشم
درست ✔
نادرست ✘


✔ (5n^2 - 6n =θ (n^2
✔ (n!=θ(n^n
✔ (2n^2*2 +nlogn = θ(n^2*2^2
✔ (Σi^2=θ(n(n+1)
✔ (n^2 * 6+2^n=θ(n^2
✘ (10n^2 +9= Ο(n^2
✘ (n^3*2^n+6^2*3^n=Ο(n^3*2^n

[arash691]

اولا" تو مبحث پیچیدگی زمانی الگوریتم ها باید ضریب رشد توابع ریاضی رو بلد باشین که به صورت زیر هستش :


log ( n ) < [ log( n ) ]^ n < n^ عدد < k ^ n (k>1) < n! < n^ متغیر

- Big O :

بیگ او کران بالای یک تابع میتونه باشه یعنی هر تابع که بهت دادن بیگ او اون تابع میتونه خودش و یا یک تابع

دیگری که رشد اون بیشتر باشه بیگ او تابع باشه : بطور مثال اگه داشته باشیم


T(n) = n

بیگ او تابع میتونه :
O(n) یا مثلا" یک تابعی باشه که رشدش بیشتر باشه مثلا"
O(n^2)

- Ω :
کران پایین تابع رو مشخص میکنه . یعنی هر تابع که داشته باشیم امگای بزرگش Ω میتونه خودش باشه یا یه

تابع دیگه با مقدار رشد کمتر :


T(n) = n^2

کران پایین میتونه
Ω(n^2) یا Ω(n)

- o :
او کوچک مثل او بزرگ هستش با این تفاوت که کران بالا رو برای تابع به صورت اکید در نظر میگیره یعنی او کوچک یک تابع هر تابعی با رشد بیشتر از اون تابع میتونه باشه

- ω :
امگای کوچک هم مثل امگای بزرگ عمل میکنه با این تفاوت که کران پایی تابع رو به صورت اکید در نظر میگیره و خود تابع نمیتونه کران پایین خودش باشه و فقط توابعی میتونن کران پایین اون تابع باشن که رشدشون کمتر باشه از تابع

- θ :
تتای یک تابع میاد بین کران بالا و پایین حرکت میکنه یعنی تتای یک تابع میتونه یک تابع باشه که هم کران پایین هم کران مابین هم کران بالا تابع باشه

بطور مثال :
T(n) = (n^2)


θ(n^2)

[ffarzadd]

اولا" تو مبحث پیچیدگی زمانی الگوریتم ها باید ضریب رشد توابع ریاضی رو بلد باشین که به صورت زیر هستش :


log ( n ) < [ log( n ) ]^ n < n^ عدد < k ^ n (k>1) < n! < n^ متغیر

- Big O :
,.......

θ(n^2)
مرسی بابت توضیحتون- الان مسئلی که هست توضیحتون کم بود- اگه میشه واضحتر و با مثال بیشتری باشه-
لطف میکنید