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

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

• لباس پوشیده
• تمیز
• خوب تغذیه شده

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

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

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

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

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

int[] numbers = new int[100];
// ..заполняем массив числами

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 ما نگاهی بیندازید ). اگر اکنون اولین عدد در لیست ما عدد باشد و عدد y را در ابتدای لیست وارد کنیم، تنها چیزی که نیاز است این است: х

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

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

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

وحشت نکنید! :) اگر کلمه "لگاریتمی" باعث می شود که سخنرانی را ببندید و بیشتر بخوانید، چند دقیقه صبر کنید. در اینجا هیچ مشکل ریاضی وجود نخواهد داشت (در جاهای دیگر چنین توضیحات زیادی وجود دارد) و ما تمام مثال ها را "روی انگشتان" تجزیه و تحلیل خواهیم کرد. تصور کنید که وظیفه شما یافتن یک عدد خاص در یک آرایه 100 عددی است. به طور دقیق تر، بررسی کنید که آیا اصلا وجود دارد یا خیر. به محض یافتن شماره مورد نیاز، جستجو باید متوقف شود و ورودی "شماره مورد نیاز یافت شد!" باید در کنسول نمایش داده شود. شاخص آن در آرایه = ....” چگونه چنین مشکلی را حل می کنید؟ در اینجا راه حل واضح است: شما باید عناصر آرایه را یکی یکی تکرار کنید، با اولین (یا آخرین) شروع کنید و بررسی کنید که آیا عدد فعلی با عدد مورد نظر مطابقت دارد یا خیر. بر این اساس، تعداد اقدامات به طور مستقیم به تعداد عناصر موجود در آرایه بستگی دارد. اگر 100 عدد داشته باشیم، باید 100 بار به عنصر بعدی برویم و عدد را برای یک مسابقه 100 بار بررسی کنیم. اگر 1000 عدد وجود داشته باشد، 1000 مرحله بررسی وجود خواهد داشت. این بدیهی است که پیچیدگی خطی، O(N) است . اکنون یک توضیح به مثال خود اضافه می کنیم: آرایه ای که در آن باید عددی را پیدا کنید به ترتیب صعودی مرتب شده است . آیا این چیزی را برای وظیفه ما تغییر می دهد؟ ما هنوز هم می توانیم عدد مورد نظر را با نیروی بی رحمانه جستجو کنیم. اما ما می توانیم به جای آن از الگوریتم جستجوی دودویی معروف استفاده کنیم . در ردیف بالای تصویر یک آرایه مرتب شده را می بینیم. در آن ما باید عدد 23 را پیدا کنیم. به جای تکرار روی اعداد، به سادگی آرایه را به 2 قسمت تقسیم می کنیم و عدد متوسط ​​را در آرایه بررسی می کنیم. عددی که در سلول 4 قرار دارد را پیدا می کنیم و آن را بررسی می کنیم (ردیف دوم در تصویر). این عدد 16 است و ما به دنبال 23 هستیم. عدد فعلی کمتر است. این یعنی چی؟ اینکه همه اعداد قبلی (که تا عدد 16 قرار دارند) نیازی به بررسی ندارند : قطعاً از اعداد مورد نظر ما کمتر خواهند بود، زیرا آرایه ما مرتب شده است! بیایید جستجو را در بین 5 عنصر باقی مانده ادامه دهیم. توجه کنید:ما فقط یک بررسی انجام داده ایم، اما نیمی از گزینه های ممکن را قبلا حذف کرده ایم. فقط 5 عنصر باقی مانده است. ما مرحله خود را تکرار می کنیم - دوباره آرایه باقی مانده را بر 2 تقسیم می کنیم و دوباره عنصر میانی را می گیریم (خط 3 در شکل). این عدد 56 است و بزرگتر از عدد مورد نظر ما است. این یعنی چی؟ اینکه ما 3 گزینه دیگر را کنار می گذاریم - خود عدد 56 و دو عدد بعد از آن (قطعاً بزرگتر از 23 هستند، زیرا آرایه مرتب شده است). فقط 2 عدد برای بررسی باقی مانده است (آخرین ردیف در شکل) - اعداد با شاخص های آرایه 5 و 6. ما اولین آنها را بررسی می کنیم، و این همان چیزی است که به دنبال آن بودیم - عدد 23! شاخص آن = 5! بیایید به نتایج الگوریتم خود نگاه کنیم و سپس پیچیدگی آن را درک خواهیم کرد. (به هر حال، اکنون متوجه شدید که چرا به آن باینری گفته می شود: ماهیت آن تقسیم مداوم داده ها بر 2 است). نتیجه چشمگیر است! اگر با استفاده از جستجوی خطی به دنبال عدد مورد نظر بودیم، به 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) افزایش یافت. پیچیدگی الگوریتم جستجوی دودویی لگاریتمی است ، یا در نماد Big-O، O(log n) است . چرا به آن می گویند؟ لگاریتم معکوس توان است. لگاریتم باینری برای محاسبه توان 2 استفاده می شود. برای مثال، ما 10000 عنصر داریم که باید با استفاده از جستجوی دودویی از آنها عبور کنیم. اکنون شما یک عکس جلوی چشمان خود دارید و می دانید که برای این کار حداکثر 14 بررسی لازم است. اما اگر تصویری جلوی چشمان شما نباشد و باید تعداد دقیق بررسی های لازم را محاسبه کنید، چه؟ کافی است به یک سوال ساده پاسخ دهیم: عدد 2 را به چه قدرتی باید رساند تا نتیجه به دست آمده >= تعداد عناصر در حال بررسی باشد؟ برای 10000 قدرت 14 خواهد بود. 2 تا توان 13 خیلی کم است (8192) اما 2 به توان 14 = 16384 ، این عدد شرایط ما را برآورده می کند (>= تعداد عناصر آرایه است). ما لگاریتم را پیدا کردیم - 14. به این تعداد چک نیاز داریم! :) الگوریتم ها و پیچیدگی آنها موضوعی بسیار گسترده است که نمی توان در یک سخنرانی گنجانده شود. اما دانستن آن بسیار مهم است: در بسیاری از مصاحبه ها مشکلات الگوریتمی دریافت خواهید کرد. برای تئوری می توانم چندین کتاب را به شما توصیه کنم. یک مکان خوب برای شروع « الگوریتم‌های غوغایی » است: اگرچه مثال‌های کتاب به زبان پایتون نوشته شده‌اند، زبان و مثال‌های کتاب بسیار ساده هستند. بهترین گزینه برای یک مبتدی و همچنین حجم کمی دارد. خواندن جدی تر: کتاب های رابرت لافورت و رابرت سدویک . هر دو به زبان جاوا نوشته شده اند که یادگیری را برای شما کمی آسان می کند. بالاخره شما با این زبان کاملا آشنا هستید! :) برای دانش آموزانی با پیشینه ریاضی خوب، بهترین گزینه کتاب توماس کورمن است . اما شما فقط به تئوری بسنده نمی کنید! "دانستن" != "توانستن" شما می توانید حل مسائل الگوریتم را در HackerRank و Leetcode تمرین کنید . مشکلات از آنجا اغلب حتی در هنگام مصاحبه در گوگل و فیس بوک مورد استفاده قرار می گیرند، بنابراین قطعاً خسته نخواهید شد :) برای تقویت مطالب سخنرانی، به شما توصیه می کنم یک ویدیوی عالی در مورد Big-O را در YouTube تماشا کنید. شما را در سخنرانی های بعدی می بینم! :)