خانه / نماد (O(n – ساختمان های داده و الگوریتم در جاوا

نماد (O(n – ساختمان های داده و الگوریتم در جاوا

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

خوب تو بخش مقدمه یه چیزای مختصری در مورد الگوریتم ها فهمیدیم که اگه یه جمع بندی بکنیم میشه الگوریتم ها مجموعه ای از دستورات کانلا واضح و دقیق که پایان پذیرندو هدف خاصی دنبال می کنن و ورودی خروجی دارند البته این و در نظر بگیریم که الگوریتم ها می تونن به تعداد زیاد ورودی داشته باشن یا اینکه اصلا ورودی نداشته باشن ولی حتما باید خروجی داشته باشن.حالا الگوریتم باید از دو جنبه سنجیده بشه یکی حافظه مورد نیاز برای اجرای الگوریتم و اون یکی زمان لازم برای اجرای الگوریتمه.

حالا کدوم مهم تره

خوب خوشبختانه با وجود پیشرفت روز افزون تکنولوژی کامپیوتر ها و تجهیزات دیجیتال حافظه ها رفته رفته ظرفیتشون بیشتر شده و میشه گفت الان به حدی رسیده که میشه ازش تا حد زیادی صرف نظر کرد اما مورد دوم یعنی پیچیدگی زمانی و زمان اجرای الگوریتم خیلی مهمه و هر کسی که الگوریتمی طراحی می کنه باید از نظر پیچیدگی زمانی حواسش باشه که الگوریتم بهینه بشه.

حالا خود پیچیدگی زمانی به چی بستگی داره

خوب یواش یواش با این مقدمه هایی که گفتیم به عنوان مطلب نزدیک میشیم پیچیدیگی زمانی به چند عامل بستگی داره که یکی یکی بررسی می کنیم:

  • سخت افزار
  • کامپایلر
  • اندازه ی ورودی
  • ترتیب ورودی
  • پیچیدگی الگوریتم

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

کامپایلرم که مترجم زبان مورد نظر به زبان قابل فهم برای کامپیوتره پس این هم تا حد زیادی دست خودمون نیست مثلا برنامه ی نوشته به زبان C سریع تر از پاسکاله.

خوب مورد سومم که اندازه ی ورودیه این یعنی مثلا با یه الگوریتم مشابه یه آرایه با صد عضو سریع تر یک آرایه با هزار عضو مرتب میشه.

ترتیب ورودی ام به این مربوط میشه که الگوریتم در چه حالتیه در واقه ما سه حالت داریم Best case , Average case, Worst case یعنی اگه مثلا آرایه مرتب باشه یعنی در حالت Best case ولی اگه کاملا نامرتب باشه در حالته Worst case و زمان بیشتره میبره تا مرتب بشه.

اما می رسیم به اصلی ترین مورد یعنی پیچیدگی الگوریتم این بسته به هنر طراح الگوریتم داره مثلا تعداد زیادی الگوریتم جستجو داریم که باید سریع ترین و انتخاب کنیم.

حالا منظور از(O(n چیه؟

خوب تا حالا در مورد الگوریتم ها پیچیدگی زمانی بحث کردیم اما ما به یه نماد نیاز داریم که پیچیدگی زمانی الگوریتم هارو مقایسه کنیم و از (O(n استفاده می کنیم و این در واقع بدترین حالت اتفاق افتادن الگوریتم هستش.بیاید یه مثال و بررسی کنیم.

خوب دستور خط اول یک بار اجرا می شه و هم چنین int i ولی حلقه ی for، به تعداد 1+ n بار و دستور داخلش n بار دستور return هم یک بار پس اگه t زمان فرضی اجرای هر دستور باشه به این حالت میشه:

T(n) = 1 * t + 1 * t + (n +1) t + n * t + 1 * t

حالا اگه t رو ثابت و برابر یک در نظر بگیریم حاصل میشه 2n + 4 که میشه از چهار و ضریب دو صرف نظر کرد چون در مقیاس بزرگ زیاد تاثیری نداره پس پیچیدگی زمانی این الگوریتم (O(n این صرفا یه مثال ساده بود برای درک مطلب . البته این و بگم به غیر از نماد O بزرگ نماد های دیگه ای هم وجود دارند ولی معمولا چون این نماد برای بیان بدترین حالت اتفاق افتادن الگوریتم به کار می ره از این استفاده میشه.

خوب حالا که با پیچیدگی الگوریتم ها آشنا شدیم از مر حله ی بعدی برای هر الگوریتمی که بیان می کنیم پیچیدگی زمانی شم بررسی می کنیم که بدونیم کدوم به صرفه تره.

خوب در آخر بازلازم می دونم بگم که اگر فکر می کنید مطالب این سایت برای کسی مفیده حتما بهش معرفی کنید اگه سوال و انتقاد و پیشنهادی ام دارین تو بخش نظرات مطرح کنین و اطمینان داشته باشین جواب داده میشه.

درباره amir hemmati asl

amir hemmati asl

این آموزش جدید رو هم از دست نده

آموزش شبیه سازی مدار مرتبه اول RC با نرم افزار متلب + ویدیو آموزشی

مدار مرتبه اول یعنی چی؟!!! مدار مرتبه اول یعنی یه مدار معمولی شامل مقاومت ها …

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *