سوال : مرتبه اجرایی

[f_cpuf]

سلام:لبخندساده:
من در مورد مرتبه اجرایی سوالی دارم اگر راهنمایی کنید ممنون میشوم.
من پیچیدگی زمان را متوجه شدم اما در مورد مرتبه زمانی مشکل دارم.:گریه::ناراحت:
من میدانم که T(n)=5n-4 از مرتبه n است و میتوانیم بگوییم که O(n) iاست.

مشکل من با تعریفی است که ارائه شده است بدین صورت که:
تعریف:f(n)=O(g(n)) iمیباشد اگر و فقط اگر به ازای مقادیر ثابت
و منفی از C و n0 ، f(n) i برای تمامی مقادیر بزرگتر یا مساوی Cg(n) iباشد یعنی:

EC,n0>0 : An >= n0 f(n) <= Cg(n)
EC به معنی آن است که حداقل یک C وجود دارد.
An به معنای همه مقادیر n میباشد.

بعد از آن در یک مثال بیان کرده است که:(تو یک کتاب!:لبخند:)

3n+3=O(n) iمیباشد چرا که اگر C=4 و n0=2 فرض کنیم، داریم:
برای 3n+3 <= 4n : n >=2
بعد گفته است که:
توجه کنید رابطه فوق برای n=1 صادق نیست ولی طبق تعریف کافی است n0 ی
وجود داشته باشد (حداقل یک n0) که از آن به بعد f(n) <= Cg(n) iباشد.
در این مثال میتوانیم n0 را برابر 3 یا 4 یا بیشتر نیز در نظر بگیریم.
همچنین C را میتوانیم 5 یا 6 یا بیشتر بگیریم.
------------------------------------------------------
1- حال سوال من این است که اصلا منظور از EC و An و n0 و C چیست؟!:متفکر:
2- در نظر گرفت اعداد برای این متغیر ها بر چه اساسی است؟ آیا برای پیدا کرده مرتبه اجرایی
هر عبارتی باید اینگونه عمل کرد؟
3- برای Ө و Ω هم اگر امکانش هست توضیحی بدهید.

از اساتید میخواهم که اگر امکان دارد توضیح دهند.

[accepted]

Θ( g(n) ) = { f(n) : there exist positive

constants c1, c2, and n0 such that

0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n) for all n ≥ n0 }

in tarife dorosteshe

[accepted]

O( g(n) ) = { f(n): there exist positive

constants c and n0 such that

0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

inam tarife O

[accepted]

Ω( g(n) ) = { f(n): there exist positive

constants c and n0 such that

0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

age mikhay, tozih bedam

[accepted]

در واقع این رابطه بین درجه هاشون برقراره که:



O( g(n) ) ≥ Θ( g(n) ) ≥ Ω( g(n) )


Ω درجه ش کمترمساوی درجه Θ

و درجه Θ کمترمساوی درجه O هست

[f_cpuf]

ممنون بابت جوابت.

همون طوریکه قبلا گفتم مشکل من با تعریفش هست!:ناراحت::گریه:

منظور از n0 و C چیست؟ ضریبه؟!:متفکر:

اگر توضیح بیشتری بدی ممنون میشم.

[amir.ardroudi]

:تشویق::تشویق: