پیچیدگی فضایی (Space Complexity) و فضای کمکی (Auxiliary Space) — به زبان ساده

در این مطلب، به مفاهیم «پیچیدگی فضایی» (Space Complexity) و «فضای کمکی» (Auxiliary Space) پرداخته شده و تفاوت آن‌ها با یکدیگر مورد بررسی قرار گرفته است. عبارت پیچیدگی فضایی، بسیاری از مواقع به اشتباه به جای فضای کمکی به کار می‌رود و بنابراین، درک مفهوم صحیح هر یک از این موارد و تفاوت آن‌ها با یکدیگر، بسیار حائز اهمیت است. در ادامه، تعریف صحیح فضای کمکی و  پیچیدگی فضایی بیان شده است.

فضای کمکی (Auxiliary Space)

فضای کمکی، یک فضای «اضافی» (Extra) یا «موقتی» (Temporary) است که توسط الگوریتم مورد استفاده قرار می‌گیرد. حافظه استفاده شده توسط کامپیوتر در زمان اجرای یک برنامه، به ویژه هنگامی که محدودیت‌های محیطی وجود داشته باشند (مثلا در دستگاه‌های موبایل) بسیار حائز اهمیت است.

فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity در فرادرس

کلیک کنید

برای مثال، اگر نیاز به ساخت آرایه‌هایی با سایز n باشد، نیاز به فضای کمکی (O(n است. اگر، ورودی یک آرایه دوبُعدی از اندازه n x n باشد، نیاز به فضای کمکی (O(n² خواهد داشت. فضای «پشته» (Stack)، در فراخوانی‌های بازگشتی زیاد درگیر می‌شود، زیرا برنامه نیازمند فضای اضافی است.

1int sum(int sum) 
2{ 
3   if (n <= 0) 
4       return 0; 
5   return n + sum(n-1); 
6}

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

     Sum(5)
	->sum(4)
            ->sum(3)
	        ->sum(2)
	            ->sum(1)
	       	        ->sum(0)

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

1// A non-recursive code that makes n calls 
2// but takes O(1) extra space. 
3int pairSumSequence(int n) 
4{ 
5    int sum = 0; 
6    for (int i=0; i<n; i++) 
7        sum += pairSum(i, i+1); 
8    return sum; 
9} 
10  
11int pairSum(int a, int b) 
12{ 
13    return a + b ; 
14}

در این مثال، (O(n فراخوانی برای pairSum وجود دارد. ولی با توجه به اینکه، این فراخوانی‌ها به طور هم‌زمان در پشته فراخوانی وجود ندارد، تنها نیاز به فضای (O(1 است.

پیچیدگی فضایی (Space Complexity)

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

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

کلیک کنید

برای مثال، اگر فردی بخواهد الگوریتم‌های مرتب‌سازی استاندارد را بر مبنای فضایی که هر یک مورد استفاده قرار می‌دهند با یکدیگر مقایسه کند، فضای کمکی نسبت به پیچیدگی زمانی معیار بهتری است. «مرتب‌سازی ادغامی» (Merge Sort) از فضای کمکی (O(n استفاده می‌کند، «مرتب‌سازی درجی» (Insertion Sort) و «مرتب‌سازی هرمی» (Heap Sort) از فضای کمکی (O(1 استفاده می‌کنند. پیچیدگی فضایی همه این الگوریتم‌های مرتب‌سازی از درجه (O(n است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• آموزش طراحی الگوریتم
• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^