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

زمان ثابت

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

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

در زیر چند نمونه کد اجرا شده در زمان ثابت آورده شده است:

Int index = 5; int item = list; اگر(شرط درست است) سپسدیگربرخی از عملیات را با زمان اجرای ثابت انجام دهید برای i = 1 به 100 برای j = 1 به 200 برخی از عملیات را با زمان اجرای ثابت انجام می دهد

اگر تی(n) برابر است با O( مقداری ثابت)، این معادل است تی(n) O(1) است.

زمان لگاریتمی

زمان لگاریتمی، اگر تی(n) = O(log n) . از آنجایی که کامپیوترها از سیستم اعداد باینری استفاده می کنند، 2 به عنوان پایه لگاریتم استفاده می شود (یعنی log 2 n). با این حال، زمانی که تعویض پایهلگاریتم log a nو ورود ب nفقط با یک عامل ثابت که در علامت O-big کنار گذاشته می شود، تفاوت دارند. بنابراین O(log n) نماد استاندارد برای الگوریتم های زمان لگاریتمی است، صرف نظر از پایه لگاریتم.

الگوریتم‌هایی که در زمان لگاریتمی اجرا می‌شوند معمولاً هنگام انجام عملیات روی درخت‌های باینری یا هنگام استفاده از جستجوی دودویی یافت می‌شوند.

الگوریتم های O(log n) بسیار کارآمد در نظر گرفته می شوند زیرا با افزایش تعداد عناصر، زمان عملیات هر عنصر کاهش می یابد.

یک مثال بسیار ساده از چنین الگوریتمی تقسیم یک رشته به نصف، نیمه دوم دوباره به نصف تقسیم می شود و غیره. این زمان O(log n) طول می کشد (که n طول رشته است، در اینجا فرض می کنیم که console.logو str.substringزمان ثابت بگیرید). به این معنی که برای افزایش تعداد چاپ، طول خط باید دو برابر شود.

// تابع چاپ بازگشتی نیمه سمت راست یک خط var right = تابع (str) (var length = str. length; // تابع کمکی var help = تابع (شاخص) ( // بازگشت: چاپ نیمه سمت راستاگر (شاخص< length ) { // کاراکترها را از فهرست تا انتهای خط چاپ کنیدکنسول. log(str. substring (شاخص، طول)); // فراخوانی بازگشتی: تابع کمکی را با سمت راست فراخوانی کنیدکمک (ریاضی سقف ((طول + شاخص ) / 2 )); ) ) کمک ( 0 ); )

زمان پلیلوگ

گفته می شود که الگوریتم اجرا می شود زمان چندلاگ، اگر تی(n) = O((log n) ک) برای برخی ک. به عنوان مثال، مسئله ترتیب ضرب ماتریس را می توان در زمان چند لگاریتمی توسط ماشین رم موازی .

زمان زیر خطی

گفته می شود که الگوریتم اجرا می شود زمان زیر خطی، اگر تی(n) = o( n). به طور خاص، این شامل الگوریتم‌های پیچیدگی زمانی ذکر شده در بالا، و همچنین موارد دیگری مانند جستجوی گروور با پیچیدگی O( n ½).

الگوریتم‌های معمولی که در عین دقیق بودن، هنوز در زمان زیرخطی عمل می‌کنند، از موازی‌سازی فرآیندها (مانند الگوریتم NC 1 برای محاسبه تعیین‌کننده یک ماتریس)، محاسبات غیرکلاسیک (مانند جستجوی گروور) استفاده می‌کنند یا از یک فرض تضمین شده در مورد ساختار ورودی (مانند مواردی که در زمان لگاریتمی اجرا می شوند، الگوریتم های جستجوی دودویی و بسیاری از الگوریتم های پردازش درختی). با این حال، ساختارهای رسمی، مانند مجموعه ای از تمام رشته ها که دارای بیت 1 در موقعیت تعیین شده توسط اولین بیت های log(n) رشته هستند، می توانند به هر بیت ورودی بستگی داشته باشند اما همچنان در زمان زیرخطی باشند.

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

از آنجایی که چنین الگوریتمی باید پاسخی را بدون خواندن کامل داده های ورودی تولید کند، به روش های دسترسی مجاز در جریان ورودی بسیار وابسته است. به طور معمول برای جریانی که یک رشته بیتی است ب 1 ,...,b k، فرض بر این است که الگوریتم می تواند مقداری را در زمان O(1) درخواست کند b iبرای هرکس من.

الگوریتم های زمانی زیرخطی معمولاً احتمالی هستند و تنها یک راه حل تقریبی ارائه می دهند. الگوریتم های زمان اجرا زیرخطی به طور طبیعی هنگام تحقیق به وجود می آیند چک های اموال.

زمان خطی

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

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

زمان شبه خطی

گفته می شود که الگوریتم در زمان شبه خطی اجرا می شود اگر تی(n) = O( nورود به سیستم ک n) برای مقداری ثابت ک. زمان خطی-لگاریتمی یک مورد خاص با ک= 1. با استفاده از نماد ضعیف O، این الگوریتم ها Õ( n). الگوریتم های زمانی شبه خطی نیز o( n 1+ε) برای هر ε > 0 و سریعتر از هر چند جمله ای در کار می کند n

الگوریتم هایی که در زمان شبه خطی اجرا می شوند، علاوه بر الگوریتم های خطی- لگاریتمی که در بالا ذکر شد، عبارتند از:

• مرتب سازی ادغام در محل، O( nورود به سیستم 2 n)
• مرتب سازی سریع، O( nورود به سیستم n)، در نسخه احتمالی دارای بدترین زمان اجرای خطی-لگاریتمی است. نسخه غیر احتمالی فقط برای اندازه گیری پیچیدگی به طور متوسط ​​زمان اجرای خطی-لگاریتمی دارد.
• Heapsort، O( nورود به سیستم n) مرتب سازی ادغامی، مرتب سازی درونی، مرتب سازی درختی باینری، مرتب سازی صاف، مرتب سازی یک نفره، و غیره. در بدترین حالت
• تبدیل فوریه سریع، O( nورود به سیستم n)
• محاسبه ماتریس های Monge، O( nورود به سیستم n)

زمان خطی-لگاریتمی

خطی-لگاریتمی یک مورد خاص از زمان شبه خطی با توان است ک= 1 در عبارت لگاریتمی.

تابع خطی-لگاریتمیتابعی از فرم است nورود به سیستم n(یعنی محصول خطیو اصطلاحات لگاریتمی). آنها می گویند که الگوریتم کار می کند زمان خطی-لگاریتمی، اگر تی(n) = O( nورود به سیستم n) . بنابراین، جمله خطی لگاریتمی سریعتر از جمله خطی، اما کندتر از هر چند جمله ای رشد می کند. nبا مدرک به شدت بیشتر از 1.

در بسیاری از موارد، زمان عملیات nورود به سیستم nصرفاً نتیجه اجرای عملیات Θ(log n) nیک بار. برای مثال، مرتب‌سازی درختی باینری با قرار دادن هر عنصر در آرایه‌ای به اندازه n یکی پس از دیگری، یک درخت دودویی ایجاد می‌کند. از زمان عملیات درج به درخت جستجوی باینری متعادلزمان O(log) را می گیرد n، کل زمان اجرای الگوریتم خطی-لگاریتمی خواهد بود.

انواع مقایسهبرای بدترین حالت حداقل به یک عدد لگاریتمی خطی از مقایسه نیاز دارد، زیرا log( n!) = Θ( nورود به سیستم n) طبق فرمول استرلینگ. همان زمان اجرا اغلب از معادله تکرار ناشی می شود تی(n) = 2 تی(n/2) + O( n).

زمان زیر درجه دوم

چند نمونه از الگوریتم های زمان چند جمله ای:

زمان چند جمله ای به شدت و ضعیف

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

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

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

هر الگوریتمی با این دو ویژگی را می توان با جایگزینی عملیات حسابی با الگوریتم های مربوط به انجام عملیات حسابی روی ماشین تورینگ به یک الگوریتم زمانی چند جمله ای تقلیل داد. اگر مورد دوم از شرایط بالا برآورده نشود، این دیگر درست نخواهد بود. با توجه به یک عدد صحیح (که حافظه متناسب با n را در ماشین تورینگ اشغال می کند)، می توان آن را با n عملیات با استفاده از توان مکرر محاسبه کرد. با این حال، حافظه ای که برای نمایش استفاده می شود 2 2 n (\displaystyle 2^(2^(n)))، متناسب 2 n (\displaystyle 2^(n))، و به جای چندجمله ای، به طور نمایی به حافظه استفاده شده برای ورودی بستگی دارد. از این رو، انجام این محاسبات در زمان چند جمله ای در ماشین تورینگ غیرممکن است، اما می توان آنها را در تعداد چند جمله ای از عملیات حسابی انجام داد.

برعکس، الگوریتم‌هایی وجود دارند که در تعداد مراحل ماشین تورینگ محدود به طول چند جمله‌ای ورودی کدگذاری‌شده باینری کار می‌کنند، اما در تعداد عملیات‌های حسابی محدود شده توسط چند جمله‌ای در تعداد اعداد ورودی کار نمی‌کنند. الگوریتم اقلیدسی برای محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح یک مثال است. برای دو عدد صحیح a (\displaystyle a)و b (\displaystyle b)زمان اجرای الگوریتم محدود است O ((log ⁡ a + log ⁡ b) 2) (\displaystyle O((\log \ a+\log \ b)^(2)))مراحل ماشین تورینگ این عدد چند جمله ای از اندازه نمایش دودویی اعداد است a (\displaystyle a)و b (\displaystyle b)، که تقریباً می تواند به عنوان نشان داده شود log ⁡ a + log ⁡ b (\displaystyle \log \a+\log \b). در عین حال، تعداد عملیات حسابی را نمی توان به تعداد اعداد صحیح در ورودی محدود کرد (که در این مورد ثابت است - فقط دو عدد در ورودی وجود دارد). با توجه به این نکته، الگوریتم در زمان کاملاً چند جمله ای عمل نمی کند. به موقععملکرد الگوریتم به کمیت ها بستگی دارد a (\displaystyle a)و b (\displaystyle b)و نه فقط تعداد اعداد صحیح در ورودی.

اگر الگوریتمی در زمان چند جمله‌ای اجرا شود، اما در زمان چند جمله‌ای اجرا شود، گفته می‌شود که در زمان اجرا می‌شود. زمان چند جمله ای ضعیف. یک مثال معروف از مسئله ای که یک الگوریتم چند جمله ای ضعیف برای آن شناخته شده است، اما یک الگوریتم کاملاً چند جمله ای شناخته شده نیست، برنامه ریزی خطی است. زمان چند جمله ای ضعیف را نباید با زمان شبه چند جمله ای اشتباه گرفت.

کلاس های سختی

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

• : طبقه ای از مسائل حل پذیری قابل حل در ماشین تورینگ قطعی در زمان چند جمله ای.
• : کلاس پیچیدگی مسائل حل پذیری که در یک ماشین تورینگ غیر قطعی در زمان چند جمله ای قابل حل هستند.
• ZPP: کلاس پیچیدگی مسائل حل پذیری که با خطای صفر در ماشین تورینگ احتمالی در زمان چند جمله ای قابل حل هستند.
• : کلاس پیچیدگی مسائل حل پذیری که با خطاهای یک طرفه در ماشین تورینگ احتمالی در زمان چند جمله ای قابل حل هستند.
• BPPماشین تورینگ احتمالی در زمان چند جمله ای
• BQP: کلاس پیچیدگی مسائل حل پذیری که با خطاهای دو طرفه در ماشین تورینگ کوانتومی در زمان چند جمله ای قابل حل هستند.

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

زمان ابر چند جمله ای

آنها می گویند که الگوریتم کار می کند زمان ابرچند جمله ای، اگر تی(n) در بالا با چند جمله ای محدود نمی شود. این زمان برابر است با ω( n ج) برای همه ثابت ها ج، جایی که n- پارامتر ورودی، معمولا تعداد بیت های ورودی.

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

واضح است که الگوریتمی که از منابع نمایی استفاده می کند، ابرچند جمله ای است، اما برخی از الگوریتم ها بسیار ضعیف ابرچند جمله ای هستند. مثلا، تست سادگی Adleman-Pomeranz-Roumeli*برای زمان کار می کند n O(log log n) بر nورودی بیت این رشد سریعتر از هر چند جمله ای به اندازه کافی بزرگ است n، اما اندازه ورودی باید بسیار بزرگ شود تا چند جمله ای درجه پایین بر آن غالب نباشد.

الگوریتمی که به زمان ابرچند جمله ای نیاز دارد خارج از کلاس پیچیدگی قرار دارد. پایان نامه کوبهاماستدلال می کند که این الگوریتم ها غیرعملی هستند، و در بسیاری از موارد چنین هستند. از آنجایی که مشکل برابری کلاس های P و NP حل نشده است، در حال حاضر هیچ الگوریتمی برای حل مسائل NP-complete در زمان چند جمله ای شناخته شده نیست.

زمان شبه چند جمله ای

الگوریتم ها زمان شبه چند جمله ایالگوریتم هایی هستند که کندتر از زمان چند جمله ای اجرا می شوند، اما نه به سرعت الگوریتم های زمان نمایی. بدترین زمان اجرای الگوریتم شبه چند جمله ای است ج. یک الگوریتم کلاسیک معروف برای فاکتورگیری یک عدد صحیح، نهشبه چند جمله ای است، زیرا زمان اجرا را نمی توان به صورت نمایش داد 2 O ((log ⁡ n) c) (\displaystyle 2^(O((\log n)^(c))))برای برخی ثابت ج. اگر ثابت "c" در تعریف الگوریتم زمانی شبه چند جمله ای 1 باشد، یک الگوریتم زمانی چند جمله ای و اگر کمتر از 1 باشد، یک الگوریتم زمانی زیرخطی بدست می آوریم.

الگوریتم‌های زمان شبه چند جمله‌ای معمولاً هنگام تقلیل یک مسئله NP-hard به مسئله دیگر به وجود می‌آیند. به عنوان مثال، می توانید یک مسئله NP-hard، مثلاً 3SAT را بگیرید و آن را به یک مشکل دیگر B کاهش دهید، اما اندازه مشکل تبدیل می شود. 2 O ((log ⁡ n) c) (\displaystyle 2^(O((\log n)^(c)))). در این مورد، کاهش ثابت نمی کند که مسئله B NP-hard است، فقط نشان می دهد که هیچ الگوریتم چند جمله ای برای B وجود ندارد، مگر اینکه یک الگوریتم شبه چند جمله ای برای 3SAT (و سپس برای همه - مشکلات) وجود داشته باشد. به همین ترتیب، مشکلاتی وجود دارد که برای آنها الگوریتم های شبه چند جمله ای زمان را می شناسیم، اما برای آنها الگوریتم های زمان چند جمله ای را نمی شناسیم. چنین مشکلاتی در الگوریتم های تقریبی ظاهر می شوند. مثال معروف مسئله اشتاینر جهت دار است که برای آن یک الگوریتم شبه چند جمله ای تقریبی با ضریب تقریب وجود دارد. O (log 3 ⁡ n) (\displaystyle O(\log ^(3)n))(که در آن n تعداد رئوس است)، اما وجود یک الگوریتم زمان چند جمله ای یک مسئله باز است.

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

QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\displaystyle (\mbox(QP))=\bigcup _(c\in \mathbb (N))(\mbox(DTIME))(2^ ((\log n)^(c))))

ارتباط با مشکلات NP-complete

در نظریه پیچیدگی، مسئله حل نشده برابری بین کلاس های P و NP می پرسد که آیا همه مسائل در کلاس NP دارای الگوریتم های حل چند جمله ای زمان هستند یا خیر. همه الگوریتم های شناخته شده برای مسائل NP-complete، مانند 3SAT، زمان نمایی دارند. علاوه بر این، این فرضیه وجود دارد که برای بسیاری از مسائل طبیعی NP-کامل هیچ الگوریتمی با زمان اجرای زیر نمایی وجود ندارد. در اینجا "زمان فوق نمایی" به معنای تعریف دوم ارائه شده در زیر گرفته شده است. (از طرف دیگر، بسیاری از مسائل تئوری گراف، که به طور طبیعی با ماتریس های مجاورت نشان داده می شوند، در زمان زیر نمایی قابل حل هستند، فقط به این دلیل که اندازه ورودی برابر با مجذور تعداد رئوس است.) این حدس (برای k- مشکل SAT) به عنوان شناخته شده است فرضیه زمان نمایی. از آنجایی که فرض می‌کند مسائل NP-کامل الگوریتم‌های شبه چندجمله‌ای-زمان ندارند، برخی نتایج غیرقابل تقریب در حوزه الگوریتم‌های تقریب فرض می‌کنند که مسائل NP-کامل الگوریتم‌های شبه چند جمله‌ای-زمان ندارند. به عنوان مثال، نتایج شناخته شده در مورد عدم تقریب مشکل پوشش مجموعه را ببینید.

زمان زیر نمایی

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

تعریف اول

اگر مسئله ای با الگوریتمی حل شود که لگاریتم زمان اجرای آن کمتر از هر چند جمله ای معین رشد کند، در زمان نیمه نمایی حل می شود. به طور دقیق تر، اگر برای هر ε > 0 الگوریتمی وجود داشته باشد که مسئله را در زمان O(2 n ε) حل می کند، زمان زیر نمایی دارد. مجموعه تمام این مسائل کلاس پیچیدگی را تشکیل می دهد SUBEXP، که بر حسب DTIME می توان آن را به صورت .

SUBEXP = ⋂ ε > 0 DTIME (2 n ε) (\displaystyle (\text(SUBEXP))=\bigcap _(\varepsilon >0)(\text(DTIME))\left(2^(n^(\varepsilon ))\درست))

توجه داشته باشید که در اینجا ε بخشی از داده های ورودی نیست و برای هر ε می تواند الگوریتم مخصوص به خود را برای حل مسئله وجود داشته باشد.

تعریف دوم

برخی از نویسندگان زمان زیر نمایی را به عنوان زمان اجرا 2 o ( n) . این تعریف اجازه می دهد تا زمان اجرا طولانی تر از تعریف اول باشد. نمونه ای از چنین الگوریتم زمانی زیر نمایی، الگوریتم کلاسیک معروف برای فاکتورگیری اعداد صحیح، روش غربال میدان عددی عمومی است که در حدود اجرا می شود. 2 O ~ (n 1 / 3) (\displaystyle 2^((\tilde (O))(n^(1/3))))، جایی که طول ورودی است n. مثال دیگر الگوریتم معروف برای مشکلات ایزومورفیسم گراف، که زمان کارکرد آن برابر است با 2 O ((n log ⁡ n)) (\displaystyle 2^(O((\sqrt (())n\log n)))).

توجه داشته باشید که تفاوتی دارد که الگوریتم از نظر تعداد رئوس یا تعداد یال ها زیر نمایی باشد. که در پیچیدگی پارامتریاین تفاوت با تعیین جفت، مسئله حل پذیری و پارامتر مشخص می شود ک. SUBEPTکلاسی از تمام وظایف پارامتری است که در زمان زیر نمایی در اجرا می شوند کو برای چند جمله ای در n :

SUBEPT = DTIME (2 o (k) ⋅ poly (n)) . (\displaystyle (\text(SUBEPT))=(\text(DTIME))\left(2^(o(k))\cdot (\text(poly))(n)\right).)

به طور دقیق تر، SUBEPT کلاس تمام وظایف پارامتر شده است (L , k) (\displaystyle (L,k))، که یک تابع قابل محاسبه برای آن وجود دارد f: N → N (\displaystyle f:\mathbb (N) \to \mathbb (N))با f ∈ o (k) (\displaystyle f\in o(k))و الگوریتمی که حل می کند Lدر حین 2 f (k) ⋅ پلی (n) (\displaystyle 2^(f(k))\cdot (\text(poly))(n)).

برای ارزیابی اثربخشی الگوریتم، مهمترین شاخص ها عبارتند از:

زمان اجرای الگوریتم،
- مقدار RAM مورد نیاز

امروزه به دلیل نیم قرن پیشرفت فناوری، شاخص اول (زمان اجرا) اغلب بسیار مهمتر از دومی است، بنابراین در ادامه فقط به جزئیات آن خواهیم پرداخت.

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

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

ساده‌سازی دوم، کنار گذاشتن عبارت‌های مرتبه پایین‌تر (یعنی عبارت‌هایی) است که سهم کمی در زمان اجرای کلی الگوریتم دارند. به عنوان مثال (از این پس عدد N اندازه داده های ورودی را مشخص می کند)،

\(1/6 N^3 + 20N + 16 \sim 1/6N^3\)،

به جای \(1/6N^3\) می نویسند "این الگوریتم پیچیدگی دارد \(O(N^3)\)، به جای \(3N^4\) می نویسند "این الگوریتم پیچیدگی دارد \(O(N ^4)\ )".

تعریف Big O

گفته می شود که \(f\) "O بزرگ" از \(g\) برای \(x \تا x_0\) است اگر یک ثابت \(C>0\) وجود داشته باشد به طوری که برای همه \(x\) از یک همسایگی از نقطه \(x_0\)، نابرابری \(|f(x)| \leq C|g(x)|\) برقرار است. در زیر تصویری از تعریف (محور \(x\) اندازه داده‌های ورودی است، محور \(y\) زمان اجرای الگوریتم است). می بینیم که با شروع از یک نقطه خاص، با تمایل اندازه داده های ورودی به \(\propto\) \(f(n)\) کندتر از \(g(n)\) رشد می کند و به طور کلی \(g (n)\) گویی آن را از بالا محدود می کند.

مثال ها. \(1 = O(N)، N = O(N^2).\)

همراه با تخمین های شکل \(O(N)\)، تخمین \(\Omega(N)\) (omega large) استفاده می شود. این نشان دهنده مرز پایین برای رشد تابع است. برای مثال، اجازه دهید تعداد عملیات الگوریتم با تابع \(f(N)=\Omega(N^2)\) توصیف شود. این بدان معنی است که حتی در موفق ترین حالت، حداقل \(N^2\) اقدامات انجام می شود. در حالی که تخمین \(O(N^3)\) تضمین می کند که بدترین حالت بیشتر از دستور \(N^3\) اقدامات نخواهد بود. تخمین \(\Theta(N)\) نیز استفاده می‌شود، که تخمین مجانبی بالا و پایین زمانی است که\(O(N)\) و \(\Omega(N)\) یکسان هستند.بنابراین، \(O(N)\) یک تخمین تقریبی از الگوریتم در بدترین داده ورودی است.\(\Omega(N)\) - در بهترین داده های ورودی،\(\Theta(N)\) - علامت کوتاه برای یکسان\(O(N)\) و \(\Omega(N)\).

تخمین زمان اجرا برای الگوریتم های مختلف

اجازه دهید T(N) را به عنوان زمان اجرای الگوریتم نشان دهیم. بگذارید الگوریتم مورد مطالعه به شکل زیر باشد:

1. مجموعه ای از دستورالعمل ها، که فقط شامل عملیات اساسی می شود:

بیانیه 1;
...
بیانیه k;

سپس T(N) = T(گزاره 1) + ... + T(گزاره k).

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

2. اظهارات if-else

اگر (شرط) (
دنباله عبارات 1
}
دیگر(
دنباله عبارات 2
}

در اینجا یا دنباله ای از دستورات 1 یا دنباله ای از دستورات 2 اجرا می شود، بنابراین، ما می خواهیم بدترین زمان اجرا را تخمین بزنیم، T(N) = max(T(توالی عبارات 1)، T(توالی عبارات 2)). به عنوان مثال، اگر زمان اجرای دنباله دستورات 1 O(N) و دنباله دستورات O(1) باشد، در این صورت T(N) = O(N) است.

برای (i = 0; i< N; i++) {
دنباله ای از اظهارات
}

زیرا حلقه N بار اجرا می شود، سپس دنباله ای از دستورات نیز N بار اجرا می شود. اگر T(توالی گزاره ها) = O(1)، آنگاه T(N) = O(N)*O(1) = O(N).

4. حلقه های تو در تو.

برای (i = 0; i< N; i++) {
برای (j = 0؛ j< M; j ++){
...
}
}

حلقه بیرونی N بار اجرا می شود. هر بار که حلقه بیرونی اجرا می شود، حلقه داخلی M اجرا می شود

حالا این کد را در نظر بگیرید:

برای (i = 0; i< N; i++) {
برای (j = i + 1؛ j< N; j ++){
دنباله ای از اظهارات
}
}

بیایید به تغییر در تعداد تکرارهای حلقه داخلی بسته به تکرار حلقه بیرونی نگاه کنیم.

I چرخه j (تعداد دفعات اجرا)
0 N
1 N-1
2 N-2
...
N-1 1

سپس دنباله دستورات N + N-1 + ... + 1 بار اجرا می شود. برای محاسبه سریع چنین مقادیری، فرمول های حاصل از تجزیه و تحلیل ریاضی مفید هستند، در این مورد فرمول

آن ها این الگوریتم دارای پیچیدگی \(O(N^2)\) خواهد بود.

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

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

برای (j = 0؛ j< N; j ++){

اگر زمان اجرای متد \(g(N)=O(N)\)، آنگاه \(T(N) = O(N)*O(N) = O(N^2)\).

5. جستجوی باینری (دودویی).

Int l = 0;
int u = A.length - 1
int m;
در حالی که (ل<= u) {
m = l + (u - 1)/2
اگر A[m]< k {
l = m +1;
}
در غیر این صورت اگر A[m] == k (
بازگشت m;
}
دیگر(
u = m - 1;
}
}
بازگشت -1;

جستجوی باینری به شما امکان می دهد شاخص عدد k را در یک آرایه مرتب شده پیدا کنید؛ اگر این عدد در آن نباشد، -1 برگردانده می شود. ابتدا k را با عدد وسط آرایه مقایسه می کنیم. اگر k کمتر از این عدد باشد، باید آن را در نیمه چپ آرایه، اگر بیشتر، در نیمه سمت راست جستجو کنیم. سپس k با عددی که در وسط نیمه آرایه انتخاب شده در مرحله قبل و غیره قرار دارد مقایسه می شود. با هر تکرار، فضای جستجو به نصف کاهش می یابد. این سوال مطرح می شود: در بدترین حالت چند تکرار باید انجام شود (یعنی وقتی عددی برابر با k هرگز در آرایه یافت نمی شود و هیچ داده ای برای مقایسه وجود ندارد).

می بینیم که پس از 1 تکرار، داده های \(N/2\) برای جستجوی شاخص \(k\) باقی می ماند، پس از 2 تکرار داده های \(N/4\) باقی می ماند و بعد از 3 تکرار - \( N/8\) و غیره اگر معادله \(\frac(N)(2^x)=1\ را حل کنیم در بدترین حالت تعداد تکرارها را خواهیم دانست. این معادله معادل معادله \(2^x=N\) است، بنابراین \(x=log_(2)(N)\) یا \(x=log(N)\) (به تعریف لگاریتم مراجعه کنید). بنابراین، برآورد پیچیدگی برای الگوریتم جستجوی دودویی \(O(logN)\) است.

خبر خوب این است که برای مشخص کردن زمان اجرای اکثر الگوریتم‌ها، تنها چند تابع کافی است: \(1، logN، N، NlogN، N^2، N^3، 2^N\). نمودار نرخ های مختلف رشد در زمان اجرای الگوریتم را بسته به اندازه داده های ورودی نشان می دهد:

از این نمودار، به طور خاص، مشخص است که اگر زمان اجرای الگوریتم "لگاریتمی" باشد، یعنی. الگوریتم دارای پیچیدگی \(O(logN)\) است، پس این بسیار جالب است، زیرا زمان اجرای آن با افزایش اندازه داده های ورودی بسیار کند رشد می کند، اگر زمان اجرا به صورت خطی به اندازه داده های ورودی بستگی دارد، این نیز بد نیست، اما بهتر است از الگوریتم هایی با زمان اجرای نمایی استفاده نکنید (\( O(2^N)\)) یا فقط در اندازه های داده بسیار کوچک استفاده کنید.

کلاس های P و NP

یک تابع غیرمنفی واقعی \(f(m)\) که برای مقادیر صحیح مثبت آرگومان تعریف می شود، در صورتی که یک چند جمله ای \(P(m)\) با ضرایب واقعی وجود داشته باشد، به صورت چند جمله ای محدود خوانده می شود. f(m) \leq P(m)\) برای همه \(m \در N^+\). مسائلی که الگوریتم‌هایی با زمان اجرای «چند جمله‌ای» برای آنها وجود دارد متعلق به کلاس P هستند (این مسائل معمولاً به سرعت و بدون هیچ مشکلی حل می‌شوند).

تعریف رسمییک زبان L به کلاس P تعلق دارد اگر و فقط اگر ماشین تورینگ قطعی M وجود داشته باشد به طوری که:

برای هر داده ورودی، M کار خود را در زمان چند جمله ای به پایان می رساند،
- برای همه \(x \در L\) M نتیجه 1 را ایجاد می کند،
- برای همه \(x\) که به \(L\) تعلق ندارند، M نتیجه 0 را ایجاد می کند.

مشکلات کلاس NP- کارهایی که شرط را برآورده می کنند: اگر پاسخی وجود دارد (راه حل ممکن) ، تأیید آن آسان است - بررسی کنید که آیا راه حل است یا خیر.

بیایید مثالی از یک مشکل از کلاس NP را در نظر بگیریم. اجازه دهید مجموعه ای از اعداد صحیح داده شود، به عنوان مثال، (-7، -3، -2، 5، 8). شما باید دریابید که آیا در بین این اعداد 3 عدد وجود دارد که مجموع آنها 0 می شود یا خیر. در این صورت، پاسخ "بله" است (به عنوان مثال، چنین سه گانه ای اعداد (-3،-2،5) است. اندازه مجموعه‌های اعداد صحیح افزایش می‌یابد، تعداد زیرمجموعه‌های متشکل از 3 عنصر به صورت تصاعدی افزایش می‌یابد. در همین حال، اگر به ما یک زیر مجموعه داده شود (به آن گواهی نیز می‌گویند)، به راحتی می‌توانیم بررسی کنیم که آیا مجموع عناصر آن است یا خیر. برابر با 0.

تعریف رسمی:

یک زبان L به کلاس NP تعلق دارد اگر و فقط اگر چندجمله‌ای \(p\) و \(q\) و یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که:

برای هر \(x,y\)، ماشین M روی داده های ورودی \((x,y)\) در زمان \(p(|x|)\) اجرا می شود.
- برای هر \(x \در L\) یک رشته \(y\) به طول \(q(|x|)\) وجود دارد که \(M(x,y)=1\),
- برای هر \(x\) غیر از \(L\) و تمام رشته های طول \(q(|x|)\) \(M(x,y)=0\).

تقلیل پذیری چند جمله اییا کاهش پذیری کارپ. تابع \(f_1\) به تابع \(f_2\) کاهش می یابد اگر یک تابع \(f \در P\) وجود داشته باشد به طوری که برای هر \(x\) \(f_(1)(x)=f_( 2)(f(x))\).

مسئله T نامیده می شود NP-کامل، اگر متعلق به کلاس NP باشد و هر مسئله دیگری از NP را می توان در زمان چند جمله ای به آن تقلیل داد. شاید معروف ترین مثال یک مسئله NP-complete مسئله SAT (از کلمه رضایت پذیری) باشد. اجازه دهید فرمولی حاوی متغیرهای بولی، عملگرهای "AND"، "OR"، "NOT" و پرانتز به ما داده شود. مشکل این است: آیا می توان به همه متغیرهایی که در فرمول ظاهر می شوند، مقادیر را اختصاص داد؟ دروغو درست است، واقعیبه طوری که فرمول مقدار " درست است، واقعی".

مسئله T نامیده می شود NP-hard، اگر برای آن یک مسئله NP-کامل وجود داشته باشد که در زمان چند جمله ای به T کاهش یابد. منظور ما در اینجا کاهش پذیری کوک است. کاهش مسئله \(R_1\) توسط کوک به \(R_2\) یک الگوریتم زمانی چند جمله ای است که مسئله \(R_1\) را حل می کند به شرطی که تابعی که راه حل مسئله \(R_2\) را پیدا می کند به عنوان اوراکل به آن داده شود. ، یعنی دسترسی به آن تنها یک مرحله طول می کشد.

در اینجا روابط احتمالی بین کلاس های بالا از مسائل وجود دارد (دانشمندان هنوز مطمئن نیستند که آیا P و NP یکسان هستند).

عملکرد دشواری 0 (1). در الگوریتم های پیچیدگی ثابت، اکثر عملیات در برنامه یک یا چند بار انجام می شود. هر الگوریتمی که همیشه (صرف نظر از اندازه داده) به زمان یکسانی نیاز دارد، پیچیدگی ثابتی دارد.

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

تابع پیچیدگی 0 (N 2)، 0 (N 3), 0(№) - تابع پیچیدگی چند جمله ای: تعداد عملیات با مربع افزایش می یابد ن.در حالت کلی، بسته به پیچیدگی مسئله، می تواند O(A^) باشد. این تابع پیچیدگی یک چرخه پیچیده را مشخص می کند.

عملکرد دشواری O(Log 2 (A0), 0 (N log2 (A0). این زمانی است که الگوریتم هایی کار می کنند که یک مسئله بزرگ را به بسیاری از مسائل کوچک تقسیم می کنند و سپس با حل آنها، راه حل ها را ترکیب می کنند.

تابع پیچیدگی 0 (e N).الگوریتم هایی با پیچیدگی نمایی اغلب از رویکردی به نام نیروی بی رحم ناشی می شوند.

تابع پیچیدگی 0 (M) -تعداد عملیات متناسب با فاکتوریل رشد می کند ن.

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

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

برای مثال، الگوریتمی برای پردازش عناصر آرایه در نظر بگیرید.

برای /": = 1 به نشروع کن

پیچیدگی این الگوریتم در باره(A)، از آنجایی که بدنه حلقه A بار اجرا می شود، و پیچیدگی بدنه حلقه 0(1) است. اگر یک حلقه درون حلقه دیگری تودرتو باشد و هر دو حلقه به اندازه متغیر مشابهی بستگی داشته باشند، کل طرح با پیچیدگی درجه دوم مشخص می شود.

برای /: = 1 به نانجام دهید برای j: = 1 به نشروع کن

پیچیدگی این برنامه 0 (N 2).

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

• - ورودی یک آرایه (شما باید عناصر A را بخوانید).
• - بزرگترین عنصر را جستجو کنید (شما باید مقایسه A - 1 انجام دهید).
• - خروجی نتیجه (شما نیاز به خروجی یک عدد یا رشته).

بیایید تعداد عملیات A + (A - 1) + 1 = 2A را اضافه کنیم، یعنی. وجود دارد

چنان ثابت که برای هر A تعداد عملیات از CA تجاوز نمی کند. بنابراین، پیچیدگی الگوریتم 0 (A) است.

مثال 2.بیایید پیچیدگی برنامه ای را تخمین بزنیم که از صفحه کلید وارد یک آرایه می شود و عنصری با خاصیت معین (مثلاً برابر با مقدار معین) در آن پیدا می کند. الگوریتم شامل مراحل زیر است:

• - ورودی آرایه (عملیات ورودی)؛
• - جستجوی عنصری با خاصیت معین (عنصر می‌تواند نزدیک‌تر به ابتدای آرایه یا در انتهای آن قرار گیرد؛ اگر عنصر وجود نداشته باشد، برای اطمینان از این موضوع باید تمام مقایسه‌های A انجام شود).
• - خروجی نتیجه

در بهترین حالت، الگوریتم مشخص شده به عملیات A + 2 (ورودی کل آرایه، یک مقایسه واحد، خروجی)، در بدترین حالت (زمانی که چنین عنصری وجود ندارد، عملیات 2A + 1) نیاز دارد. اگر A عدد بزرگی باشد، برای مثال در مرتبه 10 6، آنگاه می توان از وحدت صرف نظر کرد. بنابراین، پیچیدگی الگوریتم برابر است با 0 (N).

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

• - وارد کردن یک کلمه (یک عملیات)؛
• - سازماندهی چرخه:
  • 1) برای هر کاراکتر، جایگزین آن را در جدول پیدا کنید (اگر جدول مرتب نشده باشد و هیچ خاصیتی که جستجو را آسانتر می کند ندارد، در بدترین حالت به شما نیاز خواهید داشت. اسعملیات برای یک کاراکتر اگر عنصر جستجو شده در انتهای آن باشد).
  • 2) خروجی نماد پیدا شده؛
• - پایان چرخه

تعداد کل عملیات 1 + (S+)L.در صورت به اندازه کافی بزرگ اسو Lواحدها را می توان نادیده گرفت، و معلوم می شود که تابع پیچیدگی الگوریتم داده شده است O(S L).

مثال 4.اجازه دهید تابع پیچیدگی الگوریتم ترجمه اعداد طبیعی را تعریف کنیم 1 V به سیستم اعداد باینری (بدون عملیات ورودی و خروجی داده). الگوریتم شامل مراحل زیر است:

• - حلقه بزنید تا نتیجه تقسیم یک عدد بر 2 برابر 0 شود:
• - عدد را بر 2 تقسیم کنید و بقیه را به خاطر بسپارید.
• - نتیجه تقسیم را به عنوان یک عدد جدید بگیرید.
• - پایان چرخه

تعداد کل عملیات از 1 + log 2 A تجاوز نمی کند. بنابراین، الگوریتم توصیف شده دارای پیچیدگی است. 0 (og 2 N).

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

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

در این مقاله، من پیشنهاد می کنم معیارهای اصلی ارزیابی را شرح دهیم و مثالی از ارزیابی یک الگوریتم ساده ارائه دهم. Habrahabr قبلاً اطلاعاتی در مورد روش های ارزیابی الگوریتم ها دارد، اما عمدتاً دانش آموزان دبیرستانی را هدف قرار می دهد. این نشریه را می توان بسط آن مقاله دانست.

تعاریف

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

مفاهیم پیچیدگی در وجود دارد بدترین, میانگینیا بهترین سناریو. معمولاً پیچیدگی در بدترین حالت تخمین زده می شود.

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

ترتیب افزایش پیچیدگی الگوریتم ها

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

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

انواع تخمین مجانبی

O – برآورد بدترین حالت

پیچیدگی را در نظر بگیرید f(n) > 0، تابعی از همان ترتیب g(n) > 0، اندازه ورودی n > 0.
اگر f(n) = O(g(n))و ثابت وجود دارد c > 0, n 0 > 0، آن
0 < f(n) < c*g(n),
برای n > n 0.

تابع g(n) در این مورد یک تخمین مجانبی دقیق از f(n) است. اگر f(n) تابعی از پیچیدگی الگوریتم باشد، ترتیب پیچیدگی به صورت f(n) – O(g(n)) تعریف می شود.

این عبارت کلاسی از توابع را تعریف می کند که تا یک فاکتور ثابت سریعتر از g(n) رشد نمی کنند.

نمونه هایی از توابع مجانبی

f(n)	g(n)
2n 2 + 7n - 3	n 2
98n*ln(n)	n*ln(n)
5n+2	n
8	1

Ω – برآورد برای بهترین حالت

با این حال، این تعریف شبیه به بدترین برآورد است
f(n) = Ω(g(n))، اگر
0 < c*g(n) < f(n)

Ω(g(n))دسته ای از توابع را تعریف می کند که کندتر از تابع رشد نمی کنند g(n)تا یک عامل ثابت

Θ – برآورد برای مورد متوسط

فقط شایان ذکر است که در این مورد تابع f(n)در n > n 0همه جا بین c 1 *g(n)و c 2 *g(n)، که در آن c یک عامل ثابت است.
مثلاً وقتی f(n) = n 2 + n; g(n) = n 2.

معیارهای ارزیابی پیچیدگی الگوریتم ها

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

سختی زمان برای DEXتوسط مقدار تعیین می شود l (Op)، جایی که ای ص- مقدار عملوند
پیچیدگی خازنی در LVKتوسط مقدار تعیین می شود l (M)، جایی که م- اندازه سلول حافظه

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

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

Void main() (نتیجه int = 1؛ int i؛ const n = ...؛ برای (i = 2؛ i<= n; i++) result = result * n; }

پیچیدگی زمانی با معیار وزن دهی یکنواخت

کافی است به سادگی تعیین کنیم که اندازه ورودی یک مسئله معین است n.
تعداد مراحل - (n - 1).

بنابراین، پیچیدگی زمانی تحت RVC برابر است بر).

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

در این مرحله، باید عملیاتی را که باید ارزیابی شوند برجسته کنید. اولاً، اینها عملیات مقایسه هستند. دوم، عملیات تغییر متغیرها (جمع، ضرب). عملیات واگذاری در نظر گرفته نمی شود زیرا فرض می شود که آنی هستند.

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

1) من<= n

در مرحله i-ام معلوم می شود ورود (n).
از آنجایی که مراحل (n-1)، پیچیدگی این عملیات خواهد بود (n-1)*log(n).

2) i = i + 1

در مرحله i-ام معلوم می شود ورود به سیستم (i).
.

3) نتیجه = نتیجه * i

در مرحله i-ام معلوم می شود ورود به سیستم ((i-1)!).
بنابراین، مجموع است .

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

پیچیدگی خازنی با معیار وزن یکنواخت

اینجا همه چیز ساده است. باید تعداد متغیرها را بشمارید. اگر مشکل از آرایه استفاده کند، هر خانه از آرایه یک متغیر در نظر گرفته می شود.
از آنجایی که تعداد متغیرها به اندازه ورودی بستگی ندارد، پیچیدگی برابر خواهد بود O (1).

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

در این مورد، باید حداکثر مقدار قابل ذخیره در یک سلول حافظه را در نظر بگیرید. اگر مقدار تعریف نشده باشد (به عنوان مثال، زمانی که عملوند i > 10)، آنگاه فرض می شود که نوعی مقدار حدی وجود دارد. Vmax.
در این مشکل، متغیری وجود دارد که مقدار آن بیشتر از آن نیست n(i)و متغیری که مقدار آن تجاوز نمی کند n! (نتیجه). بنابراین نمره است O(log(n!)).

نتیجه گیری

مطالعه پیچیدگی الگوریتم ها کار بسیار جذابی است. در حال حاضر، تجزیه و تحلیل ساده ترین الگوریتم ها در برنامه های درسی تخصص های فنی (به طور دقیق، جهت تعمیم یافته "انفورماتیک و علوم کامپیوتر") درگیر در علوم کامپیوتر و ریاضیات کاربردی در زمینه IT گنجانده شده است.
بر اساس پیچیدگی، کلاس های مختلفی از وظایف متمایز می شوند: پ, NP, NPC. اما این دیگر مشکلی در نظریه تحلیل مجانبی الگوریتم ها نیست.

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

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

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

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، پیچیدگی الگوریتم ما با استفاده از بر). این نماد برای استفاده در آینده بهتر است به خاطر بسپارید - همیشه برای الگوریتم هایی با پیچیدگی خطی استفاده می شود. لطفاً توجه داشته باشید: ما در اینجا اصلاً در مورد چیزهای مختلف "متغیر" صحبت نمی کنیم: سرعت اینترنت ، قدرت رایانه ما و غیره. هنگام ارزیابی پیچیدگی یک الگوریتم، این به سادگی معنی ندارد - به هر حال ما کنترلی روی آن نداریم. 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 (1)بیایید اکنون به نمونه‌های بیشتر «برنامه‌نویس» نگاه کنیم :) فرض کنید یک آرایه از 100 عدد به شما داده شده است، و وظیفه این است که هر یک از آنها را به کنسول خروجی دهید. شما یک حلقه for معمولی می نویسید که این کار را انجام می دهد int numbers = new int [100]; // .. آرایه را با اعداد پر کنیدبرای (int i: اعداد) ( System. out. println (i) ؛ ) پیچیدگی الگوریتم نوشته شده چیست؟ خطی، O(N).تعداد اقداماتی که برنامه باید انجام دهد بستگی به این دارد که دقیقاً چند عدد به آن منتقل شده است. اگر 100 عدد در آرایه وجود داشته باشد، 100 عمل (خروجی روی صفحه) وجود خواهد داشت، اگر 10000 عدد در آرایه وجود داشته باشد، 10000 عمل باید انجام شود. آیا الگوریتم ما قابل بهبود است؟ خیر در هر صورت ما باید انجام دهیم N از آرایه عبور می کندو N خروجی را روی کنسول اجرا کنید. بیایید به مثال دیگری نگاه کنیم. عمومی استاتیک void main (Args رشته) (LinkedList < Integer> اعداد = لینکدلیست جدید< >() ؛ شماره. افزودن (0, 20202); شماره. add(0, 123); شماره. add(0, 8283); ) ما یک LinkedList خالی داریم که تعدادی اعداد را در آن وارد می کنیم. ما باید پیچیدگی الگوریتم را برای درج یک عدد در LinkedList در مثال خود تخمین بزنیم و اینکه چگونه به تعداد عناصر موجود در لیست بستگی دارد. پاسخ خواهد بود O (1) - پیچیدگی ثابت. چرا؟ لطفا توجه داشته باشید: هر بار یک عدد را در ابتدای لیست درج می کنیم. علاوه بر این، همانطور که به یاد دارید، هنگام درج یک عدد در LinkedList، عناصر به جایی منتقل نمی شوند - پیوندها دوباره تعریف می شوند (اگر ناگهان فراموش کردید که چگونه LinkedList کار می کند، به یکی از ما نگاه کنید). اگر اکنون اولین عدد لیست ما عدد x باشد و عدد y را در ابتدای لیست درج کنیم، تنها چیزی که نیاز است x است. قبلی = y; y قبلی = پوچ y بعدی = x; برای این مرجع لغو ما اهمیتی نمی‌دهیم که اکنون چند عدد در LinkedList وجود دارد- حداقل یک، حداقل یک میلیارد. پیچیدگی الگوریتم ثابت خواهد بود - O(1).

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

وحشت نکنید! :)اگر کلمه "لگاریتمی" باعث می شود که بخواهید سخنرانی را ببندید و بیشتر بخوانید، چند دقیقه صبر کنید. در اینجا هیچ مشکل ریاضی وجود نخواهد داشت (در جاهای دیگر چنین توضیحات زیادی وجود دارد) و ما تمام مثال ها را "روی انگشتان" تجزیه و تحلیل خواهیم کرد. تصور کنید که وظیفه شما یافتن یک عدد خاص در یک آرایه 100 عددی است. به طور دقیق تر، بررسی کنید که آیا اصلا وجود دارد یا خیر. به محض یافتن شماره مورد نیاز، جستجو باید متوقف شود و ورودی "شماره مورد نیاز یافت شد!" باید در کنسول نمایش داده شود. شاخص آن در آرایه = ....” چگونه چنین مشکلی را حل می کنید؟ در اینجا راه حل واضح است: شما باید عناصر آرایه را یکی یکی تکرار کنید، با اولین (یا آخرین) شروع کنید و بررسی کنید که آیا عدد فعلی با عدد مورد نظر مطابقت دارد یا خیر. بر این اساس، تعداد اقدامات به طور مستقیم به تعداد عناصر موجود در آرایه بستگی دارد. اگر 100 عدد داشته باشیم، باید 100 بار به عنصر بعدی برویم و عدد را برای یک مسابقه 100 بار بررسی کنیم. اگر 1000 عدد وجود داشته باشد، 1000 مرحله بررسی وجود خواهد داشت. این آشکارا پیچیدگی خطی است. بر). اکنون یک توضیح به مثال خود اضافه می کنیم: آرایه ای که در آن باید عددی را پیدا کنید به ترتیب صعودی مرتب شده است. آیا این چیزی را برای وظیفه ما تغییر می دهد؟ ما هنوز هم می توانیم عدد مورد نظر را با نیروی بی رحمانه جستجو کنیم. اما در عوض می توانیم از معروف استفاده کنیم الگوریتم جستجوی دودویی.
در ردیف بالای تصویر یک آرایه مرتب شده را می بینیم. در آن ما باید عدد 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. دقیقاً به همین تعداد چک نیاز داریم! :) الگوریتم ها و پیچیدگی آنها موضوعی بسیار گسترده است که نمی توان در یک سخنرانی گنجانده شود. اما دانستن آن بسیار مهم است: در بسیاری از مصاحبه ها مشکلات الگوریتمی دریافت خواهید کرد. برای تئوری می توانم چندین کتاب را به شما توصیه کنم. یک مکان خوب برای شروع «ویدیوی Big-O در YouTube» است. شما را در سخنرانی های بعدی می بینم! :)