پیچیدگی فضا و زمان در الگوریتم های رایانه

مبادله فضا-زمان در علوم کامپیوتر زندگی شما را آسان تر می کند

عکس توسط آرین درویشی در Unsplash

در این مقاله ، من درباره پیچیدگی محاسباتی که توسط Juris Hartmanis و Richard E. Stearns برای تجزیه و تحلیل دشواری یک الگوریتم توسعه داده شده است ، بحث خواهم کرد. .

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

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

فاکتور زمان معمولاً مهمتر از فضا است.

توجه: - در برنامه نویسی کامپیوتر ، شما مجاز به استفاده از 256 مگابایت برای یک مشکل خاص هستید. به اگر آرایه ای با اندازه بیش از 10⁸ ایجاد کنید ، خطا را دریافت خواهید کرد. همچنین ، نمی توانید آرایه ای با اندازه 10⁶ بسازید زیرا حداکثر فضای اختصاص داده شده به یک تابع 4 مگابایت است. ما برای حل این مشکل باید جهانی تعریف کنیم.

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

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

تصویر توسط نویسنده

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

 مرحله #01: شروع. 

 مرحله #02: ایجاد دو متغیر (a & b). 

 مرحله #03: ذخیره مقادیر صحیح در "a" و "b." -> ورودی 

 مرحله #04: ایجاد متغیری با نام "Sum." 

 مرحله 05: مجموع 'a' و 'b' را در متغیری به نام 'Sum' ذخیره کنید -> خروجی 

 مرحله 06: پایان. 

ساده است به نظر می رسد.

توجه: - اگر یک گیمر هستید ، می دانید که اندازه متوسط ​​بازی (در هارد دیسک) روز به روز همراه با بهبود زمان بارگذاری افزایش می یابد. به طور مشابه ، در وب سایت ها ، زمان بارگذاری به میزان قابل توجهی کاهش می یابد و فضای ذخیره سازی سرورهای آن روز به روز افزایش می یابد. بنابراین ، همانطور که قبلاً بحث کردیم ، از نظر فضا و زمان ، زمان نقش مهمی در مراحل توسعه هر نرم افزار ایفا می کند. > pp طبق تحقیقات انجام شده توسط نیل پاتل ، "47 درصد از مصرف کنندگان انتظار دارند که وب سایت حداکثر در دو ثانیه بارگیری شود." این دلیل احتمالی است که تقریباً همه شرکت های بزرگ سرمایه گذاری زیادی در تحقیق و نوشتن این مجموعه دستورالعمل های پیچیده انجام می دهند.

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

کارآیی - ما قبلاً در مورد اهمیت کارایی در ایجاد یک الگوریتم خوب صحبت کرده ایم. این کارآیی است که زمان محاسبه را کاهش می دهد و خروجی سریع ایجاد می کند. محدودیت - الگوریتم باید پس از اتمام تعداد مشخصی از مراحل خاتمه یابد. در غیر این صورت ، از فضای حافظه بیشتری استفاده می کند و این یک عمل بد محسوب می شود. اگر برای حلقه های نامحدود یا بازگشت مجدد ادامه یابد ، شرایط سرریز و خارج از محدوده ممکن است رخ دهد. صحت-یک الگوریتم خوب باید بدون در نظر گرفتن اندازه ورودی ارائه شده ، نتیجه صحیح را ایجاد کند.

پیچیدگی زمانی چقدر اهمیت دارد؟

پیچیدگی زمانی عمیقاً با اندازه ورودی ارتباط دارد. با افزایش اندازه ورودی ، زمان اجرا (که مدت زمان لازم برای اجرای الگوریتم است) نیز افزایش می یابد.

مثال: یک الگوریتم مرتب سازی را در نظر بگیرید.

فرض کنید ما دارای مجموعه ای از اعداد به نام A = {10، 5، 21، 6، 9}،

الگوریتم های زیادی برای مرتب سازی اعداد داده شده موجود است. اما همه آنها کارآمد نیستند. برای یافتن م effectiveثرترین روش ، باید یک تجزیه و تحلیل محاسباتی روی هر الگوریتم انجام دهیم.

لئوناردو گالر و ماتئو کیمورا یکی از بهترین تحقیقات راجع به LAMFO در مورد "مرتب سازی الگوریتم" انجام دادند.

< img src = "https://cdn-images-1.medium.com/max/426/1*Rnj5rPbL7ccE-n1cXgVKrQ.png"> معیارهای LAMFO

در اینجا برخی از مشاهدات مهم نمودار آمده است :-

این آزمون پنج مورد از پرکاربردترین الگوریتم های مرتب سازی را نشان داد: Quicksort ، مرتب سازی درج ، مرتب سازی حبابی ، مرتب سازی Shell ، Heapsort. زبان برنامه نویسی مورد استفاده برای انجام کار پایتون است و اندازه ورودی از 2500 تا 50000 متغیر است. نتایج عبارت بودند از: "الگوریتم های Shell sort و Heap Sort با وجود طول لیست ها به خوبی عمل کردند ، در طرف دیگر متوجه شدیم که Insertion sort و Bubble الگوریتم های مرتب سازی بدتر بودند و زمان محاسبه را به میزان قابل توجهی افزایش دادند. نتایج را در نمودار بالا ببینید. درک داده های ما مهمترین بخش در اجرای یک تجزیه و تحلیل موفق است.

مقدمه ای بر نشانه های بدون علامت (آسان شده)

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

بنابراین ، علامت بدون علامت چیست؟ > ما نمی توانیم دو الگوریتم را مستقیماً در کنار یکدیگر مقایسه کنیم. این بستگی زیادی به ابزارها و سخت افزاری دارد که برای مقایسه استفاده می کنیم ، مانند سیستم عامل ، مدل CPU ، تولید پردازنده و غیره. تحت تأثیر تغییرات نامحسوس در محیط سیستم قرار می گیریم.

بنابراین ، ما از تجزیه و تحلیل مجانبی برای مقایسه پیچیدگی فضا و زمان استفاده می کنیم. این دو الگوریتم را بر اساس تغییرات در عملکرد آنها در مورد افزایش یا کاهش اندازه ورودی تجزیه و تحلیل می کند.

در ابتدا سه نوع علامت بدون علامت وجود دارد:

نماد Big-Oh (O) . علامت بزرگ امگا (Ω). علامت Big Theta (Θ)-به طور گسترده استفاده می شود.

علامت Big-Oh/Big-O (O)

نماد big-O در سال 1894 توسط پل باخمن معرفی شد. او بدون بحث این بحث را در بحث خود در مورد آن معرفی کردتقریبی یک تابع. n) <= c*g (n) برای همه n> = n0}

در اینجا 'n' مقدار حد بالا را می دهد. اگر یک تابع O (n) است ، آن O (n²) ، O (n³) نیز هست.

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

توسط مدیسن استنکویچ (Dev.to)

امگا بزرگ (Ω) نماد:

 از تعریف: تابع f (n) Ω (g (n) است ) در صورت وجود اعداد مثبت c و N ، به عنوان مثال f (n) ≥ cg (n) برای همه n ≥ N. 

محدوده پایینی یک تابع را تعریف می کند - یعنی حداقل زمان یک الگوریتم حداقل مقدار خروجی (big-Ω) را برای ورودی مربوطه می دهد.

نمودار توسط Hacker Earth

Big Theta (Θ) نماد:

 در صورت وجود اعداد مثبت c1 ، c2 ، f (n) Θ (g (n)) است و N به گونه ای که c1g (n) ≤ f (n) ≤ c2g (n) برای همه n ≥ N 

محدوده پایینی و بالایی یک تابع را تعریف می کند ، یعنی در هر دو وجود دارد ، بیشترین و حداقل مرزهای یک مقدار ورودی داده شده.

نمودار توسط Hacker Earth < /img> توجه:-Big-O بر حسب ≤ و Ω بر حسب ≥ تعریف می کند. = در هر دو نابرابری گنجانده شده است. این روش محدود کردن مجموعه ای از محدوده های ممکن پایین و بالا را پیشنهاد می کند. این محدودیت با نماد Big Theta (Θ) انجام می شود.

بهترین مورد ، بدترین مورد و میانگین مورد در تحلیل بدون علامت:

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

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

از شما برای خواندن این داستان و دیدار مجدد متشکرم. در صورت داشتن هر گونه نظر ، بازخورد یا پیشنهادی در مورد آن ، نظر خود را بنویسید!

منابع

پیچیدگی فضایی یک الگوریتم - Studytonight چرا پیچیدگی زمانی ضروری است و پیچیدگی زمانی چیست؟ - Greatlearning پیچیدگی زمان و مکان - HackerEarth راهنمای کامل درک پیچیدگی زمان و مکان الگوریتم ها - جریان کد را بیاموزید چگونه سرعت صفحه را افزایش دهیم - نیل Patel الگوریتم های مرتب سازی - LAMFO

الگوریتم پیچیدگی زمانی