پیچیدگی زمانی
با توجه به نزدیکی بسیار زیاد مطالب این مبحث با پیچیدگی محاسباتی و نماد O بزرگ توصیه می‌شود ابتدا مطالب مربوط به آنها مطالعه شود و سپس برای مطالعهٔ دقیق‌تر موضوع ادامهٔ این مبحث را مطالعه نمایید.
الگوریتم‌های مختلفی برای حل یک مسئله ممکن است طراحی شده باشند. برای انتخاب بهترین الگوریتم باید معیاری جهت مقایسه کارایی الگوریتم‌ها داشته باشیم.
ارزیابی در دو مرحله انجام می‌شود:
آنالیز کارایی یک تخمین اولیه‌ است با دو معیار:
سنجیده می‌شود؛ که رفتار الگوریتم را در زمان اجرا با مجموعه‌ای از ورودی‌های منتخب توصیف می‌کنند. بعد از پیاده‌سازی الگوریتم با یک زبان برنامه‌نویسی، آمار حقیقی دربارهٔ زمان و حافظه مصرف‌شده توسط الگوریتم در هنگام اجرا جمع‌آوری می‌شود.
پیچیدگی زمانی مجموعه محدود از رابطه بین ورودی‌ها و اجرای خطوط برنامه است به گونه که با توجه به عملکرد توابع اصلی برنامه و توابع بازگشتی (مستقل یا وابسته) اندازه‌گیری کارایی مستقل از آنالیز کارایی ایجاد می‌گردد. زمان اجرای یک برنامه به موارد زیر بستگی دارد.
زمان اجرای برنامه‌ها به صورت رابطه بین بزرگی سایز ورودی و زمان مورد نیاز برای پردازش ورودی است. زمان اجرا یکی از ملاک‌های مقایسه چند الگوریتم برای حل یک مسئله است. منظور از واحد زمانی، واحدهای زمانی واقعی مانند میکرو یا نانو ثانیه نیست بلکه منظور واحدهای منطقی است که رابطه بین بزرگی (n) یک فایل یا یک آرایه و زمان مورد نیاز برای پردازش داده‌ها را شرح می‌دهد. (توجه کنید که هر دستور یک واحد زمانی اشغال می‌کند) مثلاً دستورهای؛ a=b و؛ c/d-e*; a=b هر کدام یک واحد زمانی را دربردارند.
مجموع تعداد عملکردهای اجرایی، زمان اجرای برنامه را می‌رساند و مستقل از ماشین است. یک گام یا مرحله برنامه، یک قسمت یا بخش با معنی برنامه‌است (از لحاظ مفهومی یا نحوی) که زمان اجرای آن مستقل از مشخصات نمونه‌است. بعنوان مثال تمام عبارت زیر یک مرحله‌است. return (a+b-c) / (a+b)+۴٫۰ ; بنابراین تعداد مراحل برای هر عبارت یک برنامه بستگی به؛ نوع عبارت دارد، بطوریکه در عبارات توضیحی برابر صفر و در دستور انتسابی بدون فراخوانی برابر یک است؛ و در دستورهای غیربازگشتی حلقه for, while, repeat until به تعداد تکرار حلقه در نظر گرفته می‌شود.
هدف از محاسبه پیچیدگی زمانی یک الگوریتم این است که بفهمیم نیازمندی یک الگوریتم به زمان با چه تابعی رشد می‌کند و هدف اصلی بدست آوردن این تابع رشد است. برای مثال هرچه زبان برنامه‌نویسی (مترجم) به زبان ماشین نزدیک‌تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید. زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می‌کند.
برای محاسبه پیچیدگی زمانی الگوریتم ابتدا تعداد قدم‌های الگوریتم به صورت تابعی از اندازه مسئله مشخص می‌شود، برای انجام این کار تعداد تکرار عملیات اصلی الگوریتم محاسبه می‌شود و به صورت تابع f بیان می‌شود. سپس تابع g، که مرتبه بزرگی تابع f را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می‌دهد، بدست می‌آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی‌های مختلف با استفاده از نمادها O ،Θ و Ω که در بخش بعدی با آن‌ها آشنا می‌شویم، بیان می‌شود.
زمان اجرای یک الگوریتم از مسائل مهم طراحی الگوریتم است و غالباً کارایی الگوریتم‌ها را از روی زمان اجرای آن‌ها بررسی می‌شود. همان‌طور که می‌دانیم الگوریتم عبارتست از: مجموعه‌ای از دستورها و دستورالعمل‌ها برای حل مسئله که شرایط زیر را باید دارا باشد:
الگوریتم‌ها توسط زبان برنامه‌نویسی پیاده‌سازی می‌شوند و هر الگوریتم توسط یک برنامه ارائه می‌شود هر برنامه نیز مثل الگوریتم زمان اجرای خاص خود را دارد.
عوامل دخیل در زمان اجرای برنامه:
از این عوامل سرعت سخت‌افزار و نوع کامپایلر به صورت ثابت در زمان اجرای برنامه‌ها دخیل هستند. پارامتر مهم پیچیدگی زمانی الگوریتم است که خود تابعی از اندازه مسئله است. ترکیب داده‌های ورودی نیز با بررسی الگوریتم در شرایط مختلف قابل اندازه‌گیری است. در ادامه سعی در بررسی پیچیدگی زمانی الگوریتم خواهیم داشت. برای بررسی الگوریتم تابعی به نام (T(n که تابع زمانی الگوریتم نامیده می‌شود در نظر می‌گیریم که در آن n اندازه ورودی مسئله است. مسئله ممکن است شامل چند ورودی باشد. به عنوان مثال اگر ورودی یک گراف باشد علاوه بر تعداد راس ها(n) تعداد یال‌ها (m)هم یکی از مشخصه‌های داده ورودی است. در این صورت زمان اجرای الگوریتم را با (T(n,m نمایش می‌دهیم. در صورتی که تعداد پارامترها بیشتر باشند آن‌هایی که اهمیت بیشتری در زمان اجرا دارند را در محاسبات وارد می‌کنیم و از بقیه صرف نظر می‌کنیم.
برای محاسبه تابع (T(n برای یک الگوریتم موارد زیر را باید در محاسبات در نظر بگیریم: از موارد ذکر شده در محاسبه (T(n یک الگوریتم محاسبه تعداد تکرار عملیات و توابع بازگشتی اهمیت ویژه‌ای دارند و پیچیدگی زمانی مربوط به این دو است.
مثال: تعداد کل مراحل برنامه زیر را محاسبه کنید.
کل عبارت مساوی ۲n+3 می‌شود. همان‌طور که مشاهده می‌کنید زمان اجرای هر عبارت جایگزینی یا محاسباتی را مساوی ۱ واحد زمانی فرض می‌کنیم. هم چنین دستور داخل حلقه n بار انجام می‌شود ولی آزمایش کردن شرط حلقه در خط for به تعداد n+1 بار صورت می‌گیرد. دستور Return نیز مساوی یک واحد زمانی است.
خطوط { } و نیز خط اول تعریف تابع و تعریف متغیر دستورهایی نیستند که توسط cpu اجرا شوند و زمان اجرای آن‌ها برابر صفر است.
اگر عمل اصلی را فقط خط؛ Sum=sum+I فرض کنیم آنگاه (n)=n خواهد بود.
مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می‌گردد؟
حلقه‌های for برنامه مستقل از یکدیگر هستند
T(N)=MN
مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می‌گردد؟
حلقه‌های for برنامه به یکدیگر وابسته‌اند:
تعداد اجرا شدن دستور اصلی= ۳٬۲،1... ,n(n+۱)/۲ = n
T(n)=n(n+1)/2
پیچیدگی حافظه‌ای میزان فضایی از حافظه‌است که برنامه برای اجرای کامل به آن نیاز دارد. فضای مورد نیاز در هر برنامه مجموع قسمت‌های زیر است:
در تحلیل فضای لازم روی تخمین بخش متغیر تأکید نداریم زیرا برای هر مسئله ابتدا باید مشخصات موردی را تعیین کنیم که کار دشواری است.
برای نمایش پیچیدگی الگوریتم‌ها از تعاریف زیر استفاده می‌شود:
تابع f(n) را برای n≥۰ در نظر بگیرید. می‌گوییم (f(n) = O(g(n) است اگر ثابت مثبت و حقیقی c و عدد صحیح و غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N: f(n)≤cg(n) برقرار باشد. این نماد حد بالایی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای مقادیر معین ورودی دارد.
تابع (f(n را برای n≥۰ در نظر بگیرید. می‌گوییم ((f(n) = Ω(g(n) اگر ثابت مثبت و حقیقی c و عدد صحیح و غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N: ((f(n) ≥ c(g(n) برقرار باشد. این نماد حد پایینی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر معین ورودی دارد.
تابع (f(n را برای n≥۰ در نظر بگیرید. می‌گوییم ((f(n) = Θ(f(n) است اگر ثابت‌های مثبت و حقیقی c و d و عدد صحیح غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N: c g(n) ≤f(n) ≤ d g(n) برقرار باشد. به عبارت دیگر برای تابع پیچیدگی مفروض (f(n:
این نماد حدمتوسطی برای تابع (f(n می‌دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی‌های مسئله نشان می‌دهد.
اگر زمان الگوریتم وابسته به ورودی نباشد با نماد O(۱) نشان داده می‌شود؛ و برای تحلیل الگوریتم باید به اندازه کافی الگوریتم را درک کرده باشیم تا بهترین و بدترین رفتار را تولید و محاسبه کنیم.
چون برآورد رفتار آماری ورودی‌ها امری دشوار است، در اکثر موارد به بدترین حالت قناعت می‌کنیم.
نکته. اگر الگوریتم شامل بخش‌های مختلفی باشد که هر قسمت پیچیدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پیدا کرده و بزرگترین مرتبه را به عنوان پیچیدگی کل الگوریتم در نظر می‌گیریم.
غالباً پیچیدگی (g(n یکی از توابع زیر است: n (پیچیدگی خطی)، log n (لگاریتمی)، n^a (چندجمله‌ای) و a^n که a≥۲ (نمایی).
در زیر مرتبه اجرائی چند تابع به ترتیب صعودی نوشته شده‌است.
formula_2
الگوریتم‌ها بر دو مبنای صرفه جویی در زمان، صرفه جویی در هزینه و استفاده از حافظه استوارند که اولی تحت عنوان پیچیدگی زمانی و دومی تحت عنوان پیچیدگی حافظه از آن یاد می‌شود که به ترتیب هر دو مستقل از سخت‌افزار و نوع زبان برنامه‌نویسی است و بر این اصل استوار است که دستور کلیدی الگوریتم (دستوری که در تمام تکرارهای الگوریتم وجود دارد) به ازای مقادیر گوناگون پارامتر ورودی در بدترین حالت، بهترین حالت و حالت میانگین حداقل یا حداکثر یا به‌طور متوسط چندبار اجرا می‌شوند یا چه میزان حافظه را به خود تخصیص می‌دهند.
بنابراین روش‌های گوناگونی طراحی شده‌است تا به کمک آن‌ها الگوریتم‌هایی نوشته و براساس آن‌ها برنامه‌نویسی‌هایی انجام گیرد تا بهترین کارایی از لحاظ پیچیدگی زمانی و مکانی حاصل شود که روش‌های زیر از جمله مهم‌ترین آن‌ها بوده و در کتاب طراحی الگوریتم مورد بحث قرار گرفته‌است:
برای محاسبه پیچیدگی روابط می‌توانید از قضایای زیادی استفاده نمایید که مهم‌ترین آن‌ها قضیه اصلی (قضیه اصلی واکاوی الگوریتم‌ها) است که بسیار کارآمد است. برای آن که مشخص کنیم میزان کارایی یک الگوریتم در حل یک مسئله تا چه حد است باید به تحلیل آن بپردازیم.
هنگامی که کارایی الگوریتم‌ها را بر حسب زمان تحلیل می‌کنیم، تعداد چرخه‌های واقعی CPU را تعیین نمی‌کنیم، زیرا این به کامپیوتر خاصی که الگوریتم روی آن اجرا می‌شود بستگی دارد. در عوض به معیاری نیاز داریم که مستقل از کامپیوتر، زبان برنامه‌نویسی، برنامه‌نویس و خلاصه همه جزئیات الگوریتم از قبیل افزایش اندیس حلقه‌ها و غیره باشد. به‌طور کلی تحلیل پیچیدگی زمانی یک الگوریتم عبارت است از تعیین تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می‌شود.
هنگام به‌کار بستن نظریه تحلیل الگوریتم‌ها، گاهی باید از زمان لازم برای اجرای عمل اصلی دستورهای سربار و دستورهای کنترلی روی کامپیوتری که الگوریتم را اجرا می‌کند آگاه باشیم. منظور از دستورهای سربار دستورهایی نظیر مقدار دهی اولیه پیش از شروع حلقه‌هاست. تعداد دفعاتی که این دستورها اجرا می‌شوند با تعداد ورودی افزایش نمی‌یابد.
به معنای تحلیل کارایی برحسب زمان یا حافظه است. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Kenneth H. Rosen, Discrete Mathematics and Its Applications 5th ed. McGraw Hill. Jalal Marhon Almaa - Time Travel E-Book