معمای لی‌لی، یک سوال الگوریتمی

تصور کنید کنار پنجره نشسته‌اید و در حال کدنویسی هستید. در همین حین، توجهتان به دختربچه‌ای جلب می‌شود که بیرون از آنجا مشغول بازی لی‌لی است. او با دقت روی کاشی‌های نقاشی‌شده می‌پرد—گاهی یک خانه را رد می‌کند و گاهی با پرشی بلند، دو خانه را پشت سر می‌گذارد. برای لحظه‌ای حواستان پرت میشود و از کارتان دست می‌کشید.

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

این سؤال را در یک مصاحبه‌ی الگوریتمی از من پرسیده شده بود و اولین راه‌حلی که به ذهنم رسید، استفاده از ترکیبیات بود. ابتدا باید مشخص کنیم چند پرش یک‌تایی و چند پرش دوتایی لازم است تا به خانه‌ی آخر برسیم.

مثلاً اگر ۴ خانه داشته باشیم، سه روش مختلف برای رسیدن به انتها وجود داره:

• چهار پرش یکی
• دو پرش یکی و یک پرش دوتایی
• دو پرش دوتایی پشت سر هم

اینجا بود که یادم اومد ترتیب پرش‌ها هم در تعداد حالات ممکن تأثیر داره. یه فرمول از ترکیبیات به ذهنم رسید که می‌شد با استفاده از اون، تعداد ترتیب‌های ممکن را محاسبه کرد:

تعداد کل ترتیب‌ها = فاکتوریل تعداد کل پرش‌ها تقسیم بر فاکتوریل تعداد پرش های تکراری

بعدش تعداد کل حالت‌ها را برای تمامی انتخاب‌ها محاسبه کردم. کدی که نوشتم در نگاه اول به دلیل داشتن دو حلقه، پیچیدگی زمانی O(N^2) به نظر می‌رسید، اما از اونجا که این حلقه‌ها مستقل از یکدیگر بودند، در واقع پیچیدگی زمانی آن O(N) به حساب میومد.

بعد از اینکه مسئله حل شد، شروع به بررسی تک تک جواب‌ها کردم و یه الگوییی توی مسئله ها دیدم: جواب مسئله برابر با مجموع دو جواب قبلیه! اینجا بود که به یاد تابع بازگشتی معروف فیبوناچی افتادم و تصمیم گرفتم از این روش برای حل مسئله استفاده کنم:

وقتی کدم رو تست می‌کردم، متوجه شدم که برای ورودی‌های بزرگ، کدی که نوشتم خیلی کند عمل می‌کنه. یادم افتاد که پیچیدگی زمانی تابع فیبوناچی O(2^n) هست. ایده‌ای که به ذهنم رسید استفاده از memoization بود؛ به این صورت که یک کش (cache) تعریف می‌کنیم و ورودی و خروجی تابع رو در اون ذخیره می‌کنیم. در صورتی که تابع با ورودی تکراری فراخوانی بشه، به جای محاسبه دوباره، خروجی مستقیم از کش خوانده می‌شه، این کار سرعت اجرای کد رو بالا میبره.

کدی که نوشته بودم برای ورودی‌های کوچک از راه‌حل ترکیبیاتی سریع‌تر عمل می‌کرد ولی برای ورودی‌های بزرگ، مثلاً برای محاسبه جواب برای ۳۰ خانه لی‌لی (n=30) خیلی کندتر بود. از یه طرف برای ورودی های بالای ۱۰۰۰ به مشکل RecursionError میخوردم.

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

این حلقه ساده تونسته بود توی تمام ورودی با یه ضریب ثابتی از راه حل ترکیبیاتی سریعتر عمل کنه همچنین پیچیدگی زمانی اون O(N) و پیچیدگی فضاییش هم O(1) بود، اینجا داشتم فکر میکردم چرا باید ترکیبیات کندتر باشه با یه یکم تحقیق فهمیدم که توی پایتون، فاکتوریل با استفاده از حلقه for حساب میشه و راه حلی که قبلا فکر میکردم O(N) بوده در اصل (N^2)O بوده، اینجا گفتم که بازم خیلی از فاکتوریل ها تکراری دارن محاسبه میشن پس اگه اونم memoize کنم احتمالا جوابم سریعتر بشه:

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

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

پ.ن ۱: برای تست سرعت الگوریتم‌ها از کتابخانه richbench استفاده کردم. جزئیات سیستمی که باهاش تست گرفتم اینها بوده:

CPU: 11th Gen Intel i5-11400H
Memory: 15694 MiB
GPU: Intel TigerLake-H GT1 [UHD Graphics]
OS: Zorin OS 17.2 x86_64
PYTHON_VERSION: 3.12.7

پ.ن ۲: برای memoization توی پایتون معمولا از @functools.cache استفاده میشه اما سر مصاحبه الگوریتمی باید بتونید خودتون کدش رو بزنید.