سلام . عیدتون مبارک باشه.
بخاطر مهم بودن بحثای هفته پیش این هفته سوالا مروری از دو هفته گذشته و یه روش خیلی پرکاربرد هستش به اسم TwoPointer.
Two Pointer : بیشتر به چشم یه بهبود دهنده ی سرعت الگوریتم ها میتونین بهش نگا کنین چون...بسته به مسئله میشه این روش رو جایگزین جستجوهای ساده ولی پرهزینه تر کرد.
بذارین با یه مثال بررسیش کنیم :
فرض کنین یه آرایه ی صعودی زیر رو داریم و دنبال 2 تا عدد از این مجموعه هستیم که مجموعشون برابر 22 باشه .
A = { 1 , 3 , 7 , 11 , 15 , 28 }
یه روش ساده و پر هزینه اینه که با یه حلقه تودرتو تمام حالتای انتخاب 2 تا عدد رو چک کنیم و ببینیم برابر 22 میشه یا نه . ولی این میشه O(n^2) و تو آرایه های بزرگ جوابگو نیست . حالا بزارین این روش رو نگاه کنیم :
i = 0 , j = 5;
while (i<j)
{
k = a[i]+a[j];
if (k == 22) { cout<<"OK"; break; }
else if (k > 22) j--;
else i++;
}
در واقع اول میایم دو تا اشاره گر اول و آخر آرایه میذاریم .
- اگه جمعشون برابر 22 بود که جواب پیدا شده.
- اگه بیشتر از 22 باشه باید جمع دو تا عدد رو کوچیکتر کنیم پس باید j رو بیاریم عقب تا روی عددای کوچیکتر بیفته .
- اگرم که کمتر باشه باید i رو ببریم جلو تا جمعشون رو بیشتر کنیم .
این الگوریتم O(n) هستش و خیلی بهتر از روش اول هستش .
مثال دوم : ترکیب دو تا آرایه مرتب:
فرض کنید 2 تا آرایه ی مرتب دارین و میخواین ترکیبشون کنین .
A = { 1 , 3 , 5 , 8 }
B = { 3 , 4 , 7 , 12 }
A + B -> C = { 1 , 3 , 3 , 4 , 5 , 7 , 8 , 12 }
میشه دو تا آرایه رو به هم وصل کرد و بعد سورتش کرد یا یکی رو تو اون یکی insert کرد. ولی با روش دو اشاره گر این کار خیلی سریعتره.
i = 0 , j=0
while (i<|A| && j<|B|)
{
if (A[i] <= B[j]) -> add A[i] to C , i++
else -> add B[j] to C , j++
}
while (i<|A|) -> add A[i] to C , i++
while (j<|B|) -> add B[j] to C , j++
مثالای دیگه :
- مسئله Book هفته پیش که براش همینجا پست گذاشتیم .
یکم پیشرفته تر :
- جمع دو تا ماتریس spars
- پارتیشن بندی QuickSort
- پیدا کردن حلقه تو لینک لیست ، ... ، یوتیوب
و ... ... ....
مسابقه امشب شروع میشه. موفق باشین
