مرتبه ی اجرایی الگوریتم ها

[feri_sharp]

سلام دوستان.
من دارم درس ساختمان داده رو دوره می کنم.
الان رسیدم به بخش مرتبه ی اجرایی، می خوام بدونم، مرتبه ی اجرایی الگوریتم های به کارمون میان؟
و اصلا نمادهایی مثل O یا Ω یا ω چجوری استفاده میشن، چرا نمادهای مختلف برای مرتبه اجرایی تعریف شدن؟

ممنون.
موفق باشید.

[feri_sharp]

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

[مسعود اقدسی فام]

این سوال جواب خیلی مفصلی داره.

اما به زبان ساده و مختصر O بدترین حالت اجرای الگوریتم، و امگا بهترین حالت رو نمایش می‎ده. تتا هم حالت متوسط یا میانگین.

[i-nostalgic]

خیلی سخت است نمی دونم
این که تو اول هر کتاب کامپیوتری اومده

[feri_sharp]

ممنون دوستان اما منظورم اینه که دونستان اینا کجا به درد می خوره؟ مثلا ما یک برنامه ای می نویسیم که به اندازه ی 100 صفحه ی A4 اندازشه، خوب، باید برای هر تابعی که می نویسیم بیایم مرتبه ی اجرایی الگوریتم رو حساب کنیم؟
کلا این نماد ها رو می شناسم روش های محاسبه رو هم می دونم. کاربردشون و می خوام

[soroushp]

ببین یکی از کاربرداش اینه که شما بیای برنامت رو بهینه سازی کنی تا از منابع دراختیارت حداکثر سود ببری - مثلا میان چندتا الگوریتم جستجو رو با هم مقایسه می کنند ، مزایا و معایب اش می گنند ، انتخاب با شماست که در چه زمانی و در چه مکانی از اون الگوریتم به خصوص استفاده کنی ...

[DelphiProgrammer]

سلام.
این نمادهای مجانبی o , O , ... برای استفاده نیستند! یک شاخصی هستند که بر اساس اون مشخص میشه که پیچیدگی یک الگوریتم چقدر هست.
مثلا شما به شما میگن bobble sort پیچیدگی n^2 داره ولی پیچیدگی quick sort در حالت متوسط برابر n*logn هست. نتیجه میگیریم که بهتر هست از quick sort مثلا مرتب سازی داده های زیاد استفاده کنیم چون اگر از مثلا از bobble sort استفاده کنیم بهینه نخواهد بود.
یا مثلا دوست شما میاد یک راه حلی برای حل یک مساله ارائه میکنه با پیچدگی n^3 بعد شما میای یک راه حلی ارائه میدی که پیچدگی اون n^2*logn هست. خوب مصلما اونی که پیچیدگی کمتری داره بهتر عمل میکنه.
البته یک موردی هم باید بهش توجه بشه. الگوریتم ها دومدل پیچیدگی دارن. یکی فضایی هست یکی زمانی. که البته بیشتر زمانی مهم هست. ولی بعضی جاها فضایی هم اهمیت پیدا میکنه.
مخلص کلام اینکه این نمادها فقط برای شاخص گذاری یک الگوریتم استفاده میشن. نه بیشتر! در حل مساله کاربردی ندارن. وقتی شما مساله رو حل کردی میتونی بیای بگی این مساله رو من با فلان پیچیدگی حل کردم و اگر بهتر از بقیه حل کرده بودی بیای بهش مباهات کنی
سعی کنید اون درس رو با دقت بخونید. از نظر من که اهمیت زیادی داره اون درس.
موفق باشید.

[i-nostalgic]

سلام.
این نمادهای مجانبی o , O , ... برای استفاده نیستند! یک شاخصی هستند که بر اساس اون مشخص میشه که پیچیدگی یک الگوریتم چقدر هست.
مثلا شما به شما میگن bobble sort پیچیدگی n^2 داره ولی پیچیدگی quick sort در حالت متوسط برابر n*logn هست. نتیجه میگیریم که بهتر هست از quick sort مثلا مرتب سازی داده های زیاد استفاده کنیم چون اگر از مثلا از bobble sort استفاده کنیم بهینه نخواهد بود.
یا مثلا دوست شما میاد یک راه حلی برای حل یک مساله ارائه میکنه با پیچدگی n^3 بعد شما میای یک راه حلی ارائه میدی که پیچدگی اون n^2*logn هست. خوب مصلما اونی که پیچیدگی کمتری داره بهتر عمل میکنه.
البته یک موردی هم باید بهش توجه بشه. الگوریتم ها دومدل پیچیدگی دارن. یکی فضایی هست یکی زمانی. که البته بیشتر زمانی مهم هست. ولی بعضی جاها فضایی هم اهمیت پیدا میکنه.
مخلص کلام اینکه این نمادها فقط برای شاخص گذاری یک الگوریتم استفاده میشن. نه بیشتر! در حل مساله کاربردی ندارن. وقتی شما مساله رو حل کردی میتونی بیای بگی این مساله رو من با فلان پیچیدگی حل کردم و اگر بهتر از بقیه حل کرده بودی بیای بهش مباهات کنی
سعی کنید اون درس رو با دقت بخونید. از نظر من که اهمیت زیادی داره اون درس.
موفق باشید.

هر چه قدر o کوچکتر باشه نمی شه نتیجه گرفت که الگوریتم خوبه مثلا quick sort اگر لیست تقریبا مرتب باشه پیچیدگی آن زیاد میشه و ...
به خاطر همین فقط سه حالت بهترین و متوسط و بدترین ارایه میشه تمام