دانشمندان کامپیوتر و توسعه دهندگان نرم افزار اغلب نیاز به ارزیابی زمان اجرای الگوریتم ها دارند. الگوریتم مجموعهای از دستورالعملها است که کامپیوتر باید آنها را برای حل یک مشکل خاص اتخاذ کند. این مجموعه مراحل باید محدود باشد، به این معنی که الگوریتم باید در نقطه ای از اجرای برنامه به پایان برسد. این مفهوم از الگوریتم ها چگونه با نماد Big-O ارتباط دارد؟
نماد Big-O چیست؟
به بیان ساده، نماد Big-O یک ابزار ریاضی است که دانشمندان کامپیوتر و توسعه دهندگان نرم افزار از آن برای ارزیابی زمان اجرای یک الگوریتم استفاده می کنند. چند توابع ریاضی محبوب وجود دارد که برای اندازهگیری زمان اجرای یک متد C# استفاده میشود. این توابع بر اساس مدت زمانی که یک عملیات خاص طول می کشد تا به هدف (ها) خود برسد، انتخاب شدند. توجه داشته باشید که این یک ابزار نظری برای اندازه گیری زمان اجرا است. اگر کسی بخواهد زمان دقیق اجرای یک الگوریتم در حال اجرا بر روی یک پردازنده خاص را بداند، باید معیارهایی برای به دست آوردن چنین اطلاعاتی بنویسد. یک پردازنده اینتل ممکن است چهارده میلی ثانیه طول بکشد تا دو عدد صحیح اضافه کند، در حالی که یک پردازنده AMD ممکن است پانزده میلی ثانیه طول بکشد تا به همان هدف برسد. بنابراین، چرا نماد Big-O را یاد بگیریم؟
نماد Big-O مفید است، اگر کسی بخواهد با استفاده از کدی که در نظر گرفته شده است، زمان اجرا را انتزاع کرده و ارزیابی کند، نه اینکه همیشه مجبور باشد هر بار که الگوریتم ارزیابی میشود، معیارهایی بنویسد. نماد Big-O روشی کاربردی تر و کلی به ما می دهد که با استفاده از هر زبان برنامه نویسی، هر کامپیوتر و هر سیستم عاملی می توان عملکرد یک الگوریتم را در سطح کد ارزیابی کرد. با در نظر گرفتن این موضوع، اجازه دهید نحوه استفاده دقیق از Big-O و عملکردهای مختلف مورد استفاده برای ارزیابی زمان اجرا را در نظر بگیریم.
وقتی نماد Big-O را می خوانیم، می گوییم که یک الگوریتم از مرتبه x است، که در آن x تابعی است که برای ارزیابی زمان اجرای یک الگوریتم خاص استفاده می شود. به عنوان مثال، هنگام اندازه گیری یک الگوریتم جستجو، ممکن است بگوییم که این الگوریتم جستجو از مرتبه n است. عبارت order of با O() نشان داده می شود، که در آن عبارت Big-O را به دست می آوریم. پرانتز حاوی تابعی است که برای اندازه گیری زمان اجرای یک الگوریتم استفاده می شود.
با در نظر گرفتن مثال بالا یک بار دیگر، ممکن است بگوییم که الگوریتم جستجوی فرضی ما یک الگوریتم O(n) است.
اجازه دهید اکنون محبوب ترین توابع مورد استفاده توسط دانشمندان کامپیوتر و توسعه دهندگان نرم افزار را در هنگام ارزیابی زمان اجرای الگوریتم ها معرفی کنیم.
ابتدا استفاده از O(1) را معرفی می کنیم. ما از این نماد برای نشان دادن الگوریتم هایی استفاده می کنیم که زمان اجرای آنها ثابت است. نمونه هایی از این الگوریتم ها شامل اضافه کردن دو عدد، انتساب متغیر، دسترسی به عناصر آرایه، دستور بازگشت و شکست و تفریق دو عدد است. با این حال، توجه داشته باشید که اظهارنامه های متغیر نباید شمارش شوند و فقط تکالیف باید شمارش شوند.
نماد دومی که استفاده می شود نماد O(lg n) است. این بدان معنی است که یک الگوریتم از مرتبه log n است، که چگونه خوانده می شود. کافی است بگوییم که الگوریتمهایی وجود دارند که تعداد عناصری را که باید روی آنها کار کنند به دو قسمت تقسیم میکنند. به همین دلیل، log پایه دو از n، که در آن n اندازه ورودی است به اختصار lg n است. الگوریتمهای معمولی که O(lg n) هستند شامل جستجوی دودویی میشوند.
نمادهای دیگری که استفاده می شوند عبارتند از O(n)، O(n lg n)، (n^2)، O(n^3)، O(2^n)، و O(n!). همانطور که در کاوش ساختار داده ها و الگوریتم ها ادامه می دهیم، با این نمادها روبرو خواهیم شد. توجه داشته باشید که ما از این نمادها برای اندازه گیری بهترین و بدترین حالت الگوریتم ها استفاده می کنیم. اندازه گیری سناریوهای موردی متوسط دشوارتر است. با بهترین و بدترین سناریوها، ما به مدت زمان اجرای یک الگوریتم در شرایط خاص اشاره می کنیم. به عنوان مثال، در مورد الگوریتم جستجوی فرضی ما، ممکن است بررسی کنیم که آیا یک آرایه خالی است یا نه. اگر چنین است، واقعاً میتوانیم بگوییم که بهترین زمان اجرای این الگوریتم O(1) است (زیرا اجرای مقایسهها به زمان مشابهی نیاز دارد). با این حال، اگر یک آرایه خالی نباشد، ممکن است بگوییم که در بدترین حالت، الگوریتم O(n) است.
اجازه دهید این مقاله را با بررسی نمونه کد C# و ارزیابی زمان اجرای آن با استفاده از نماد Big-O به پایان برسانیم.
- public int Sum(int n, List < int > elements) {
- int sum = 0; // O(1) operation
- int i = 0; // O(1) operation
- for (; i < n; i++) { // This totals to 1+2n (more details below).
- sum += elements[i]; // This totals to 3n operations.
- }
- return sum; // O(1) operation.
- }
از آنجایی که i = 0، i < n، و i++ زمان اجرای یکسانی دارند، در مجموع سه عملیات را می شماریم (سه عمل زیرا i++ میانبری برای اختصاص هر دو به متغیر i و افزودن یکی به آن است).
جمع += عناصر[i]; زمان اجرا را در نظر بگیرید و مجموع این خطوط به سه عملیات می رسد. این دو خط در اندازه ورودی n این الگوریتم ضرب می شوند، بنابراین ما 3n+3n داریم، زیرا این عملیات اجرا می شود که بستگی به بزرگی n دارد.
دستور بازگشت و انتساب متغیر sum = 0 و i = 0 را به این اضافه کنید، 3n+3n+1+1+1 = 6n+3 داریم. با این حال، وقتی نوبت به نماد Big-O می رسد، مقادیر ثابت مانند اعداد را دور می اندازیم و فقط از حروف یا توابع دیگر به عنوان پاسخ به هر تحلیل الگوریتمی استفاده می کنیم. بنابراین، برای الگوریتم Sum() ما n را به عنوان پاسخ نهایی داریم و می گوییم که الگوریتم ما یک عملیات O(n) است.
اگر بخواهیم یک تابع آنالیز مانند 3N^2 +n!+3+2 را در نظر بگیریم، میگوییم که الگوریتم ما O(n!) است، زیرا ثابتها را حذف کردیم، اما یک مرحله اضافی نیز انجام دادیم. ما بالاترین عبارت را در این مجموع انتخاب کردیم، که مرحله نهایی هنگام تجزیه و تحلیل یک الگوریتم است.
در مقالههای آینده، ساختارهای دادهای را توسعه خواهیم داد که معمولاً مورد استفاده قرار میگیرند و زمان اجرای هر یک از روشهای آن را اندازهگیری میکنیم (به عنوان مثال، اضافه کردن عناصر، مرتبسازی، جستجو و غیره. در حال حاضر، تمرین تجزیه و تحلیل الگوریتم را در نظر بگیرید)
.