مبانی نظریه پیچیدگی محاسباتی EITC/IS/CCTF

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

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

واحدهای سنتی زمان (ثانیه، دقیقه و غیره) در تئوری پیچیدگی به کار نمی روند، زیرا آنها بیش از حد به رایانه انتخاب شده و پیشرفت فناوری وابسته هستند. به عنوان مثال، یک کامپیوتر امروزی می تواند الگوریتمی را به طور قابل ملاحظه ای سریعتر از یک کامپیوتر دهه 1960 اجرا کند، با این حال، این به دلیل پیشرفت های تکنولوژیکی در سخت افزار کامپیوتر است تا کیفیت ذاتی الگوریتم. هدف نظریه پیچیدگی تعیین کمیت نیازهای زمانی ذاتی الگوریتم ها یا محدودیت های زمانی اساسی است که یک الگوریتم بر روی هر کامپیوتری اعمال می کند. این با شمارش تعداد عملیات اساسی انجام شده در طول محاسبه انجام می شود. این رویه‌ها معمولاً به عنوان مراحل نامیده می‌شوند زیرا در نظر گرفته می‌شوند که زمان ثابتی روی یک ماشین خاص دارند (یعنی تحت تأثیر مقدار ورودی نیستند).

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

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

اندازه اعداد صحیح مورد استفاده در طول محاسبات برای بسیاری از روش‌ها محدود نمی‌شود و این غیرواقعی است که فرض کنیم عملیات‌های حسابی به زمان ثابتی نیاز دارند. در نتیجه، پیچیدگی زمانی، که به عنوان پیچیدگی بیت نیز شناخته می شود، ممکن است به طور قابل توجهی بیشتر از پیچیدگی حسابی باشد. برای مثال، دشواری محاسباتی تعیین کننده یک ماتریس عدد صحیح nn برای تکنیک های استاندارد (حذف گاوسی) O(n^3) است. از آنجایی که اندازه ضرایب ممکن است به صورت تصاعدی در طول محاسبه گسترش یابد، پیچیدگی بیت روش‌های مشابه در n نمایی است. اگر این تکنیک ها همراه با محاسبات چند مدولار استفاده شوند، پیچیدگی بیت را می توان به O(n^4) کاهش داد.

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

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

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

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

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

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

مدل های محاسباتی

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

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

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

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

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

محاسبات موازی و توزیع شده

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

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

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

محاسبات کوانتومی

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

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

پیچیدگی مسئله (مرزهای پایین تر)

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

در نتیجه، هر پیچیدگی داده شده در نماد O بزرگ نشان دهنده پیچیدگی الگوریتم و مسئله همراه است.

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

برای حل اکثر مسائل، تمام داده های ورودی باید خوانده شوند، که متناسب با بزرگی داده ها زمان می برد. در نتیجه، چنین مسائلی حداقل دارای پیچیدگی خطی، یا در نماد امگا بزرگ، پیچیدگی Ω(n) هستند.

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

تعداد مقایسه‌های مورد نیاز برای یک الگوریتم مرتب‌سازی دارای کران پایینی غیرخطی Ω (nlogn) است. در نتیجه، بهترین الگوریتم‌های مرتب‌سازی کارآمدترین الگوریتم‌ها هستند زیرا پیچیدگی آنها O(nlogn) است. این واقعیت که n وجود دارد! روش های سازماندهی n چیز به این حد پایین منجر می شود. زیرا هر مقایسه این مجموعه n را تقسیم می کند! سفارشات به دو بخش، تعداد N مقایسه مورد نیاز برای متمایز کردن همه سفارشات باید 2N > n! باشد، که به معنای O(nlogn) با فرمول استرلینگ است.

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

توسعه الگوریتم

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

این یک سوء تفاهم مکرر است که در نتیجه قانون مور، که رشد تصاعدی قدرت کامپیوتری مدرن را پیش‌بینی می‌کند، ارزیابی پیچیدگی الگوریتم‌ها کمتر مرتبط می‌شود. این نادرست است زیرا افزایش قدرت امکان پردازش حجم عظیمی از داده ها (داده های بزرگ) را فراهم می کند. به عنوان مثال، هر الگوریتمی باید در کمتر از یک ثانیه به خوبی عمل کند، وقتی فهرستی از چند صد مدخل را بر اساس حروف الفبا مرتب می کند، مانند کتابشناسی یک کتاب. از سوی دیگر، برای یک میلیون ورودی (به عنوان مثال، شماره تلفن های یک شهر بزرگ)، الگوریتم های اساسی که نیاز به مقایسه O(n2) دارند باید یک تریلیون مقایسه انجام دهند که سه ساعت با سرعت 10 طول می کشد. میلیون مقایسه در ثانیه از طرف دیگر، مرتب‌سازی سریع و مرتب‌سازی ادغام فقط به مقایسه nlogn نیاز دارند (به عنوان پیچیدگی متوسط ​​برای اولی، به عنوان پیچیدگی در بدترین حالت برای دومی). این حدود 30,000,000 مقایسه برای n = 1,000,000 ایجاد می کند که با 3 میلیون مقایسه در ثانیه فقط 10 ثانیه طول می کشد.

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