تصور کنید که در کنار پنجره نشسته اید ، کد نویسی می کنید. ناگهان ، توجه شما به یک دختر کوچک در خارج از خانه جلب می شود و هاپسچ را بازی می کند. او با دقت از روی کاشی های کشیده شده پرش می کند – گاهی اوقات از یکی می پرید و گاهی اوقات جهش بزرگی را بیش از دو می کند. برای یک لحظه ، پریشان می شوید و کار خود را مکث می کنید.
در آن لحظه ، ذهن منطقی شما کنجکاو می شود: اگر کاشی های Hopscotch در یک ردیف قرار گرفته اند و دختر فقط یک یا دو قدم می پرید ، چند روش مختلف برای رسیدن به آخرین کاشی وجود دارد؟
راه حل ترکیبی
شخصی این سؤال را در مصاحبه الگوریتمی از من پرسید و اولین راه حلی که به ذهن متبادر شد استفاده از ترکیبات بود. اول ، ما باید تعیین کنیم که برای رسیدن به آخرین مربع چند پرش و چند پرش دو برابر لازم است.
به عنوان مثال ، اگر چهار مربع وجود داشته باشد ، سه روش مختلف برای رسیدن به پایان وجود دارد:
- چهار پرش منفرد
- دو پرش منفرد و یک پرش دوتایی
- دو پرش دوتایی متوالی
سپس فهمیدم که ترتیب پرش ها نیز بر تعداد کل امکانات تأثیر می گذارد. فرمولی از Combinatorics به ذهن متبادر شد که می تواند برای محاسبه تعداد ترتیبات ممکن استفاده شود:
تمهیدات کل = فاکتوریل پرش کل تقسیم شده توسط فاکتوریل پرش های مکرر
سرانجام ، من تعداد کل امکانات را برای همه راه های ممکن محاسبه کردم. در نگاه اول ، به نظر می رسید کدی که من نوشتم پیچیدگی زمانی دارد O(N²) به دلیل دو حلقه ، اما از آنجا که این حلقه ها از یکدیگر مستقل بودند ، پیچیدگی واقعی بود O(N)بشر
محلول بازگشت
پس از حل مسئله ، من نتایج را مورد تجزیه و تحلیل قرار دادم و متوجه الگویی شدم: راه حل برای تعداد مشخصی از مربع ها برابر با جمع راه حل های دو عدد قبلی بود. که زنگ می زند ، دنباله معروف فیبوناچی! بنابراین ، من تصمیم گرفتم از این رویکرد برای حل مشکل استفاده کنم:
راه حل بازگشت به یادگار
هنگام آزمایش کد من ، فهمیدم که برای ورودی های بزرگ ، اجرای من بسیار کند بود. من می دانستم که پیچیدگی زمانی عملکرد فیبوناچی است O(2ⁿ)بشر اولین پیشرفتی که به ذهن متبادر شد استفاده شد یادبود: تعریف a cache برای ذخیره ورودی ها و خروجی های عملکرد. اگر عملکرد با همان ورودی فراخوانی شده بود ، به جای محاسبه نتیجه ، خروجی را مستقیماً از حافظه نهان دریافت کنید.
این کد سریعتر از راه حل Combinatorics برای ورودی های کوچک بود ، اما برای ورودی های بزرگ ، مانند محاسبه محلول برای 30 کاشی Hopscotch ، بسیار کندتر بود. همچنین ، برای ورودی های بیشتر از 1000 ، من به یک RecursionError رسیدم.
برای راه حل حلقه
بدیهی بود که برای تعیین راه حل برای هر ورودی معین ، من فقط به دو نتیجه قبلی نیاز داشتم. این بدان معنی بود که من می توانم مشکل را با یک حلقه ساده حل کنم.
این حلقه ساده قادر بود با یک عامل ثابت از راه حل Combinatorics در تمام ورودی ها بهتر عمل کند. علاوه بر این ، پیچیدگی زمانی آن بود O(N)، و پیچیدگی فضایی آن بود O(1)بشر
راه حل ترکیبی یاد شده
در این مرحله ، من تعجب می کردم که چرا رویکرد Combinatorics کندتر است. بعد از کمی تحقیق ، فهمیدم که در پایتون ، محاسبات فاکتوریل با استفاده از یک حلقه انجام می شود ، به این معنی که آنچه در ابتدا فکر می کردم O(N) در واقع بود O(N²)بشر من همچنین متوجه شدم که بسیاری از فاکتوریل ها به طور غیر ضروری محاسبه می شوند ، بنابراین من در نظر گرفتم که آنها را به یاد بیاورم.
با کمال تعجب ، این عملکرد را بهبود نمی بخشد. در حقیقت ، این الگوریتم را به دلیل افزایش پیچیدگی فضا کندتر کرد. در این مرحله ، من بهینه سازی بیشتر را متوقف کردم و راه حل حلقه ساده را به عنوان پاسخ نهایی خود ارسال کردم.
نتایج
نظر شما چیست؟ اگر از این سؤال پرسیده شد ، چگونه به آن نزدیک می شوید؟ فکر می کنید این الگوریتم بیشتر بهینه سازی شود؟ در نظرات به من اطلاع دهید!
PS 1: من از کتابخانه 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
PS 2: در Python ، @functools.cache به طور معمول برای Memoization استفاده می شود ، اما در یک مصاحبه الگوریتمی ، شما باید خودتان آن را پیاده سازی کنید.
