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

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

• لباس پوشیده
• تمیز
• فدرال رزرو

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

1. با استفاده از ساعت زنگ دار بیدار شوید.
2. دوش بگیرید و خود را بشویید.
3. صبحانه و قهوه یا چای درست کنید.
4. بخور
5. اگر عصر قبل لباس‌هایتان را اتو نکردید، آن‌ها را اتو کنید.
6. لباس بپوش.
7. خانه را ترک کن.

این توالی اقدامات قطعا به شما امکان می دهد به نتیجه دلخواه برسید. در برنامه نویسی، ما به طور مداوم برای تکمیل وظایف کار می کنیم. بخش قابل توجهی از این وظایف را می توان با استفاده از الگوریتم هایی که قبلاً شناخته شده اند انجام داد. برای مثال، فرض کنید وظیفه شما این است: فهرستی از 100 نام را در یک آرایه مرتب کنید . این کار بسیار ساده است، اما می توان آن را به روش های مختلف حل کرد. در اینجا یک راه حل ممکن وجود دارد: الگوریتم مرتب سازی اسامی بر اساس حروف الفبا:

1. نسخه 1961 سومین دیکشنری بین المللی جدید وبستر را بخرید یا دانلود کنید.
2. هر نامی را از لیست ما در این فرهنگ لغت پیدا کنید.
3. روی یک تکه کاغذ، صفحه فرهنگ لغت که نام در آن قرار دارد را بنویسید.
4. از تکه های کاغذ برای مرتب کردن نام ها استفاده کنید.

آیا چنین ترتیبی از اقدامات وظیفه ما را انجام می دهد؟ بله، قطعاً خواهد شد. آیا این راه حل کارآمد است ؟ به ندرت. در اینجا به جنبه های بسیار مهم دیگری از الگوریتم ها می رسیم: کارایی آنها . راه های مختلفی برای انجام این کار وجود دارد. اما هم در برنامه نویسی و هم در زندگی معمولی می خواهیم کارآمدترین راه را انتخاب کنیم. اگر وظیفه شما تهیه یک تکه نان تست کره است، می توانید با کاشت گندم و دوشیدن یک گاو شروع کنید. اما این یک راه حل ناکارآمد خواهد بود - زمان زیادی را صرف می کند و هزینه زیادی را به همراه خواهد داشت. شما می توانید کار ساده خود را با خریدن نان و کره انجام دهید. اگرچه به شما اجازه می دهد تا مشکل را حل کنید، الگوریتم مربوط به گندم و گاو برای استفاده در عمل بسیار پیچیده است. در برنامه نویسی، برای ارزیابی پیچیدگی الگوریتم ها، نشانه گذاری خاصی به نام نماد O بزرگ داریم . Big O این امکان را فراهم می کند تا ارزیابی کنیم که زمان اجرای یک الگوریتم چقدر به اندازه داده ورودی بستگی دارد . بیایید به ساده ترین مثال نگاه کنیم: انتقال داده. تصور کنید که باید اطلاعاتی را در قالب یک فایل در مسافت طولانی (مثلاً 5000 مایل) ارسال کنید. چه الگوریتمی کارآمدتر خواهد بود؟ بستگی به داده هایی دارد که با آنها کار می کنید. برای مثال فرض کنید یک فایل صوتی 10 مگابایتی داریم. در این حالت کارآمدترین الگوریتم ارسال فایل از طریق اینترنت است. چند دقیقه بیشتر طول نکشید! بیایید الگوریتم خود را مجدداً بیان کنیم: "اگر می خواهید اطلاعات را در قالب فایل در فاصله 5000 مایلی انتقال دهید، باید داده ها را از طریق اینترنت ارسال کنید". عالی حالا بیایید آن را تحلیل کنیم. آیا وظیفه ما را انجام می دهد؟ خوب، بله، این کار را می کند. اما در مورد پیچیدگی آن چه می توانیم بگوییم؟ هوم، حالا همه چیز جالب تر می شود. واقعیت این است که الگوریتم ما بسیار به داده های ورودی، یعنی اندازه فایل ها بستگی دارد. اگر 10 مگابایت داشته باشیم، پس همه چیز خوب است. اما اگر بخواهیم 500 مگابایت بفرستیم چه؟ 20 گیگ؟ 500 ترابایت؟ 30 پتابایت؟ آیا الگوریتم ما از کار می افتد؟ نه، همه این مقادیر داده واقعاً قابل انتقال هستند. آیا بیشتر طول می کشد؟ بله، خواهد شد! اکنون یک ویژگی مهم الگوریتم خود را می دانیم: هر چه مقدار داده ارسالی بیشتر باشد، اجرای الگوریتم بیشتر طول می کشد . اما ما می خواهیم درک دقیق تری از این رابطه (بین اندازه داده های ورودی و زمان لازم برای ارسال آن) داشته باشیم. در مورد ما، پیچیدگی الگوریتمی خطی است. "خطی" به این معنی است که با افزایش مقدار داده های ورودی، زمان ارسال آن تقریباً به نسبت افزایش می یابد. اگر حجم داده ها دو برابر شود، زمان لازم برای ارسال آن دو برابر خواهد بود. اگر داده ها 10 برابر افزایش یابد، زمان ارسال 10 برابر افزایش می یابد. با استفاده از نماد O بزرگ، پیچیدگی الگوریتم ما به صورت O(n) بیان می شود . شما باید این نماد را برای آینده به خاطر بسپارید - همیشه برای الگوریتم هایی با پیچیدگی خطی استفاده می شود. توجه داشته باشید که ما در مورد چندین مورد که ممکن است در اینجا متفاوت باشد صحبت نمی کنیم: سرعت اینترنت، قدرت محاسباتی کامپیوتر ما و غیره. هنگام ارزیابی پیچیدگی یک الگوریتم، در نظر گرفتن این عوامل به سادگی منطقی نیست - در هر صورت، آنها خارج از کنترل ما هستند. نماد O بزرگ پیچیدگی خود الگوریتم را بیان می کند، نه "محیطی" که در آن اجرا می شود. بیایید به مثال خود ادامه دهیم. فرض کنید که در نهایت یاد می گیریم که باید فایل هایی با حجم 800 ترابایت ارسال کنیم. البته ما می‌توانیم کار خود را با ارسال آنها از طریق اینترنت انجام دهیم. فقط یک مشکل وجود دارد: در نرخ استاندارد انتقال داده خانگی (100 مگابیت در ثانیه)، تقریباً 708 روز طول می کشد. تقریبا 2 سال! :O بدیهی است که الگوریتم ما در اینجا مناسب نیست. ما به راه حل دیگری نیاز داریم! به طور غیر منتظره ای، غول فناوری اطلاعات آمازون به نجات ما می آید! سرویس Snowmobile آمازون به ما این امکان را می دهد که حجم زیادی از داده ها را در حافظه موبایل آپلود کنیم و سپس آن را با کامیون به آدرس مورد نظر تحویل دهیم! بنابراین، ما یک الگوریتم جدید داریم! "اگر می خواهید اطلاعات را در قالب فایل در فاصله 5000 مایلی انتقال دهید و ارسال آن از طریق اینترنت بیش از 14 روز طول می کشد، باید داده ها را در کامیون آمازون ارسال کنید." ما اینجا 14 روز را خودسرانه انتخاب کردیم. بیایید بگوییم این طولانی ترین دوره ای است که می توانیم صبر کنیم. بیایید الگوریتم خود را تجزیه و تحلیل کنیم. سرعتش چطوره؟ حتی اگر کامیون فقط با سرعت 50 مایل در ساعت حرکت کند، 5000 مایل را تنها در 100 ساعت طی می کند. این کمی بیشتر از چهار روز است! این بسیار بهتر از گزینه ارسال داده ها از طریق اینترنت است. و در مورد پیچیدگی این الگوریتم چطور؟ آیا خطی هم هست یعنی O(n)؟ خیر، این نیست. به هر حال، کامیون اهمیتی نمی‌دهد که چقدر آن را بارگیری می‌کنید - همچنان با همان سرعت حرکت می‌کند و به موقع می‌رسد. چه 800 ترابایت داشته باشیم، چه 10 برابر آن، کامیون همچنان ظرف 5 روز به مقصد می رسد. به عبارت دیگر، الگوریتم انتقال داده مبتنی بر کامیون پیچیدگی ثابتی دارد . در اینجا، "ثابت" به این معنی است که به اندازه داده های ورودی بستگی ندارد. یک درایو فلش 1 گیگابایتی در کامیون قرار دهید، ظرف 5 روز می رسد. در دیسک های حاوی 800 ترابایت داده قرار دهید، ظرف 5 روز به دستتان می رسد. هنگام استفاده از نماد O بزرگ، پیچیدگی ثابت با O(1) نشان داده می شود .و O(1) ، پس حالا بیایید به نمونه های بیشتری در دنیای برنامه نویسی نگاه کنیم :) فرض کنید آرایه ای از 100 عدد به شما داده شده است و وظیفه نمایش هر یک از آنها در کنسول است. شما یک حلقه معمولی می نویسید forکه این کار را انجام می دهد

int[] numbers = new int[100];
// ...fill the array with numbers

for (int i: numbers) {
   System.out.println(i);
}

پیچیدگی این الگوریتم چقدر است؟ خطی، یعنی O(n). تعداد اقداماتی که برنامه باید انجام دهد بستگی به تعداد اعداد ارسالی به آن دارد. اگر 100 عدد در آرایه وجود داشته باشد، 100 عمل (عبارت برای نمایش رشته ها روی صفحه) وجود خواهد داشت. اگر 10000 عدد در آرایه وجود داشته باشد، 10000 عمل باید انجام شود. آیا الگوریتم ما به هیچ وجه قابل بهبود است؟ خیر. مهم نیست که چه اتفاقی می افتد، ما باید N را از آرایه عبور دهیم و N دستور را برای نمایش رشته ها در کنسول اجرا کنیم. مثال دیگری را در نظر بگیرید.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

یک خالی داریم LinkedListکه چند عدد در آن وارد می کنیم. ما باید پیچیدگی الگوریتمی درج یک عدد واحد را در LinkedListمثال خود و اینکه چگونه به تعداد عناصر موجود در لیست بستگی دارد، ارزیابی کنیم. پاسخ O(1) است، یعنی پیچیدگی ثابت . چرا؟ توجه داشته باشید که هر عدد را در ابتدای لیست درج می کنیم. علاوه بر این، به یاد خواهید آورد که وقتی یک عدد را در یک عدد وارد می کنید LinkedList، عناصر به هیچ کجا حرکت نمی کنند. پیوندها (یا مراجع) به روز می شوند (اگر فراموش کرده اید که چگونه LinkedList کار می کند، به یکی از درس های قدیمی ما نگاه کنید ). اگر اولین عدد در لیست ما باشد xو عدد y را در جلوی لیست وارد کنیم، تنها کاری که باید انجام دهیم این است:

x.previous  = y;
y.previous = null;
y.next = x;

وقتی پیوندها را به‌روزرسانی می‌کنیم، اهمیتی نمی‌دهیم که در حال حاضر چند عدد وجود داردLinkedList ، یک یا یک میلیارد. پیچیدگی الگوریتم ثابت است، یعنی O(1).

پیچیدگی لگاریتمی

وحشت نکنید! :) اگر کلمه "لگاریتمی" باعث می شود این درس را ببندید و مطالعه را متوقف کنید، فقط چند دقیقه نگه دارید. هیچ ریاضی دیوانه‌واری در اینجا وجود نخواهد داشت (توضیحات زیادی مانند آن در جاهای دیگر وجود دارد)، و ما هر مثال را از هم جدا می‌کنیم. تصور کنید که وظیفه شما یافتن یک عدد خاص در یک آرایه 100 عددی است. به طور دقیق تر، باید بررسی کنید که آیا وجود دارد یا خیر. به محض یافتن تعداد مورد نیاز، جستجو به پایان می رسد و شما موارد زیر را در کنسول نمایش می دهید: "تعداد مورد نیاز پیدا شد! فهرست آن در آرایه = ...." چگونه این کار را انجام می دهید؟ در اینجا راه حل واضح است: باید عناصر آرایه را یکی یکی تکرار کنید، از اولی (یا از آخری) شروع کنید و بررسی کنید که آیا عدد فعلی با عدد مورد نظر مطابقت دارد یا خیر. بر این اساس، تعداد اقدامات به طور مستقیم به تعداد عناصر موجود در آرایه بستگی دارد. اگر 100 عدد داشته باشیم، می‌توانیم 100 بار به عنصر بعدی برویم و 100 مقایسه انجام دهیم. اگر 1000 عدد وجود داشته باشد، می تواند 1000 عدد مقایسه شود. این آشکارا پیچیدگی خطی است، یعنی O(n) . و اکنون یک اصلاح را به مثال خود اضافه می کنیم: آرایه ای که در آن باید عدد را پیدا کنید به ترتیب صعودی مرتب شده است . آیا این چیزی را در رابطه با وظیفه ما تغییر می دهد؟ ما هنوز هم می‌توانیم یک جستجوی brute-force برای عدد مورد نظر انجام دهیم. اما می‌توانیم از الگوریتم جستجوی دودویی معروف استفاده کنیم . در ردیف بالای تصویر، یک آرایه مرتب شده را می بینیم. باید عدد 23 را در آن پیدا کنیم. به جای تکرار روی اعداد، به سادگی آرایه را به 2 قسمت تقسیم می کنیم و عدد وسط را در آرایه بررسی می کنیم. عددی که در سلول 4 قرار دارد را پیدا کنید و آن را علامت بزنید (ردیف دوم در تصویر). این عدد 16 است و ما به دنبال 23 هستیم. عدد فعلی کمتر از چیزی است که به دنبال آن هستیم. معنی آن چیست؟ این بدان معناست که تمام اعداد قبلی (آنهایی که قبل از عدد 16 قرار دارند) نیازی به بررسی ندارند : تضمین شده است که کمتر از اعداد مورد نظر ما هستند، زیرا آرایه ما مرتب شده است! جستجو را در بین 5 عنصر باقی مانده ادامه می دهیم. توجه داشته باشید:ما فقط یک مقایسه انجام داده ایم، اما نیمی از گزینه های ممکن را قبلا حذف کرده ایم. ما فقط 5 عنصر باقی مانده است. ما مرحله قبلی خود را با تقسیم مجدد زیرآرایه به نصف و دوباره گرفتن عنصر میانی (ردیف سوم در تصویر) تکرار می کنیم. عدد 56 است و بزرگتر از عدد مورد نظر ما است. معنی آن چیست؟ یعنی ما 3 احتمال دیگر را حذف کرده ایم: خود عدد 56 و همچنین دو عدد بعد از آن (چون تضمین شده است که بزرگتر از 23 هستند، زیرا آرایه مرتب شده است). فقط 2 عدد برای بررسی باقی مانده است (آخرین ردیف در تصویر) - اعداد با شاخص های آرایه 5 و 6. ما اولین آنها را بررسی می کنیم و آنچه را که به دنبالش بودیم پیدا می کنیم - عدد 23! شاخص آن 5 است! بیایید به نتایج الگوریتم خود نگاه کنیم و سپس پیچیدگی آن را تحلیل خواهیم کرد. به هر حال، اکنون متوجه شده اید که چرا به این جستجوی دودویی می گویند: بر تقسیم مکرر داده ها به نصف متکی است. نتیجه چشمگیر است! اگر از جستجوی خطی برای جستجوی عدد استفاده می کردیم، تا 10 مقایسه نیاز داشتیم، اما با جستجوی دودویی، کار را تنها با 3 انجام دادیم! در بدترین حالت، 4 مقایسه وجود خواهد داشت (اگر در مرحله آخر عدد مورد نظر ما دومین احتمال باقی مانده بود نه اولی. پس پیچیدگی آن چطور؟ این نکته بسیار جالبی است :) جستجوی دودویی الگوریتم بسیار کمتر از الگوریتم جستجوی خطی (یعنی تکرار ساده) به تعداد عناصر آرایه وابسته است. با وجود 10 عنصر در آرایه، یک جستجوی خطی حداکثر به 10 مقایسه نیاز دارد، اما یک جستجوی باینری حداکثر به 4 مقایسه نیاز دارد. این تفاوت با ضریب 2.5 است. اما برای یک آرایه از 1000 عنصر ، یک جستجوی خطی تا 1000 مقایسه نیاز دارد، اما یک جستجوی باینری فقط به 10 مورد نیاز دارد ! اختلاف الان 100 برابر شده است! توجه داشته باشید:تعداد عناصر موجود در آرایه 100 برابر (از 10 به 1000) افزایش یافته است، اما تعداد مقایسه های مورد نیاز برای جستجوی باینری تنها 2.5 برابر (از 4 به 10) افزایش یافته است. اگر به 10000 عنصر برسیم ، تفاوت حتی چشمگیرتر خواهد بود: 10000 مقایسه برای جستجوی خطی و در مجموع 14 مقایسه برای جستجوی باینری. و دوباره، اگر تعداد عناصر 1000 برابر (از 10 به 10000) افزایش یابد، تعداد مقایسه ها تنها با ضریب 3.5 (از 4 به 14) افزایش می یابد. پیچیدگی الگوریتم جستجوی دودویی لگاریتمی است ، یا اگر از نماد O بزرگ استفاده کنیم، O(log n) است . چرا به آن می گویند؟ لگاریتم مانند نقطه مقابل توان است. لگاریتم باینری توانی است که برای بدست آوردن یک عدد باید عدد 2 را به آن افزایش داد. به عنوان مثال، ما 10000 عنصر داریم که باید آنها را با استفاده از الگوریتم جستجوی باینری جستجو کنیم. در حال حاضر، می توانید به جدول مقادیر نگاه کنید تا بدانید که انجام این کار حداکثر به 14 مقایسه نیاز دارد. اما اگر کسی چنین جدولی را ارائه نکرده باشد و شما باید حداکثر تعداد دقیق مقایسه ها را محاسبه کنید، چه؟ شما فقط باید به یک سوال ساده پاسخ دهید: به چه قدرتی باید عدد 2 را بالا ببرید تا نتیجه بزرگتر یا مساوی تعداد عناصری باشد که باید بررسی شوند؟ برای 10000، توان 14 است. 2 تا توان 13 خیلی کوچک است (8192)، اما 2 به توان 14 = 16384 ، و این عدد شرایط ما را برآورده می کند (بیشتر یا مساوی تعداد عناصر آرایه است). ما لگاریتم را پیدا کردیم: 14. ممکن است به این تعداد مقایسه نیاز داشته باشیم! :) الگوریتم ها و پیچیدگی الگوریتمی موضوعی بسیار گسترده است که در یک درس جای نمی گیرد. اما دانستن آن بسیار مهم است: بسیاری از مصاحبه‌های شغلی شامل سؤالاتی شامل الگوریتم‌ها می‌شود. برای تئوری می توانم چند کتاب را به شما توصیه کنم. می توانید با " الگوریتم های Grokking " شروع کنید. مثال های این کتاب به زبان پایتون نوشته شده اند اما در کتاب از زبان و مثال های بسیار ساده استفاده شده است. این بهترین گزینه برای یک مبتدی است و علاوه بر این، خیلی بزرگ نیست. از جمله خواندن های جدی تر، کتاب هایی از رابرت لافور و رابرت سج ویک داریم . هر دو به زبان جاوا نوشته شده اند که یادگیری را برای شما کمی آسان می کند. بالاخره شما با این زبان کاملا آشنا هستید! :) برای دانش آموزانی که مهارت های ریاضی خوبی دارند، بهترین گزینه کتاب توماس کورمن است . اما تئوری به تنهایی شکم شما را پر نمی کند! دانش != توانایی . می توانید حل مسائل مربوط به الگوریتم ها را در HackerRank و LeetCode تمرین کنید . وظایف این وب سایت ها اغلب حتی در هنگام مصاحبه در گوگل و فیس بوک مورد استفاده قرار می گیرند، بنابراین قطعاً خسته نخواهید شد :) برای تقویت این مطالب درسی، توصیه می کنم این ویدیوی عالی در مورد نماد O بزرگ را در YouTube تماشا کنید. در درس های بعدی می بینمت! :)