پنجره کشویی الگوریتمی است که معمولاً برای رشتهها یا آرایهها استفاده میشود، که امکان تجزیه و تحلیل زیرمجموعهای از دادهها را با استفاده از پنجرهای با اندازه ثابت یا پویا فراهم میکند. به بیان ساده، پنجره، در این مورد، یک زیر رشته یا زیرآرایه است. این پنجره را می توان در سراسر مجموعه داده به جلو منتقل کرد و به طور موثر تغییرات درون پنجره را بدون نیاز به محاسبه مجدد آن در هر بار تجزیه و تحلیل کرد. به عنوان مثال، از این الگوریتم می توان برای یافتن زیرآرایه ای با حداقل طول که مجموع عناصر آن بزرگتر یا مساوی یک عدد معین N است یا برای یافتن طولانی ترین رشته فرعی بدون تکرار کاراکترها استفاده کرد.
کارایی الگوریتم از این واقعیت ناشی می شود که هر عنصر فقط یک بار مورد بررسی قرار می گیرد، بنابراین به پیچیدگی خطی O(n) می رسد. این یک مزیت قابل توجه نسبت به روش brute force است که به یک حلقه تودرتو نیاز دارد و منجر به پیچیدگی درجه دوم O(n²) می شود.
مراحل اساسی الگوریتم
- با مقداردهی اولیه نشانگرهای چپ و راست، مرزهای پنجره را تنظیم کنید. این نشانگرها اساساً به عنوان متغیرهایی برای شاخص های چپ و راست پنجره عمل می کنند. به عنوان مثال، در آرایه [1,2,3,4]، نشانگر سمت چپ در 1 و نشانگر سمت راست در 2 به پنجره اشاره می کنند [2,3]. به طور معمول، اشاره گرها در موقعیت اولیه رشته/آرایه تنظیم می شوند.
2) تغییر/بسط پنجره را شروع کنید. نشانگر سمت راست را به …