سوال: تعداد n-1 عدد غیر تکراری با مقادیر 1 تا n داده شده اند. برنامه ای بنویسید که عددی از بازه 1 تا n که در بین این n-1 عدد نیست (عدد گمشده) را بیابد.
پاسخ: کار را با یک مثال شروع میکنیم تا مطمین شویم که مساله را درست فهمیده ایم (فهم مساله). مثلا اگر 7 عدد غیر تکراری در بازه 1 تا 8 بصورت زیر داشته باشیم، عدد گمشده بین آنها 6 می باشد.
برای یافتن پاسخ مساله ابتدا روش جستجوی کامل را بررسی می کنیم (راه حل جستجوی کامل). برای این کار با استفاده از یک حلقه تکرار هر بار به دنبال یکی از اعداد 1 تا n درون لیست اعداد می گردیم. مقداری که در لیست پیدا نشود جواب مورد نظر می باشد. برای این کار در بدترین حالت عدد گم شده n است که در این صورت در آخرین تکرار حلقه یافت می شود. از آنجا که در هر تکرار باید مقداره همه عناصر لیست را با یک مقدار مقایسه نماییم، تعداد کل مقایسه ها (n*(n-1 می باشد. بنابر این پیچیدگی محاسباتی این روش (O(n^2 می باشد.
این روش کند است و روی یک لیست طولانی بسیار زمان می برد. اشکال این روش آن است که هر بار کل لیست را می پیماید و از مشاهدات در دورهای قبلی استفاده ای نمی کند. در عین حال بخاطر نامرتب بودن داده ها نمی توان روش جستجوی کامل را مستقیما بهبود داد (یافتن ایراد راه حل).
بنابر این در ادامه برای راه حل بهتر بررسی می کنیم که آیا اگر لیست را مرتب کنیم الگوریتم تندتر می شود؟ با مرتب کردن لیست فوق به یک لیست جدید مانند لیست زیر می رسیم.
با دقت در لیست فوق می فهمیم که تا قبل از مقدار گم شده، هر عدد i در موقعیت i-1 در لیست قرار گرفته باشد (اندیس لیست از صفر شروع می شود). بنابر این برای یک راه حل بهتر می توانیم لیست اعداد را مرتب کنیم (ارایه راه حل بهتر). سپس از یک حلقه تکرار که از ابتدای لیست (اندیس 0) تا انتهای آن ( اندیس n-2) استفاده می کنیم. اگر عدد i+1 در اندیس i نبود آنگاه مقدار گمشده را (مقدار i+1) یافته ایم. تکه کد زیر این الگوریتم را پیاده می کند. برای محاسبه پیچیدگی محاسباتی این الگوریتم، یک اشتباه رایج این است که فراموش کنیم که محاسبات انجام شده در تابع sort (خط 2) را در نظر بگیریم و فکر کنیم چون این الگوریتم تنها دارای یک حلقه است که n-1 بار تکرار می شود، پیچیدگی محاسباتی کل برنامه (O(n است. اما در واقع بخاطر اینکه خود تابع sort دارای پیچیدگی محاسباتی ((O(n*log(nمی باشد، کل برنامه نیز با سرعت ((O(n*log(n اجرا می شود.
راه حل با استفاده از مرتب سازی به اندازه ای که فکرش را میکردیم سریع نبود. در ادامه تفکر برای یافتن راه حل خطی ((O(n) را ادامه می دهیم (ارایه راه حل بهتر). برای پیدا کردن روش بهینه کافی است به این نکته توجه کنیم که یک فرمول برای محاسبه مجموع همه مقادیر از 1 تا n وجود دارد. این فرمول S=n * (n+1)/2 می باشد. از آنجا که عدد گم شده در این حاصل جمع وجود ندارد، می توان آن را بر اساس تفاوت بین S و مجموع عناصر لیست پیدا کرد. تکه کد زیر پیاده سازی این روش را نشان می دهد.
تابع sum (خط 2) مجموع عناصر لیست را محاسبه می کند. پیچیدگی محاسباتی این الگوریتم برابر با پیچیدگی تابع sum است که خطی (O(n است.
