투 포인터 알고리즘 시간 복잡도 :O(n)

투 포인터 알고리즘이란

리스트에 순차적으로 접근해야할 때 두개의 점 위치를 기록하면서 처리하는 알고리즘

1차원 배열을 각자 다른 값을 가리키는 2개의 포인터를 사용해 가면서 값을 얻는 형태

시간 복잡도 O(n) 인 이유

왼쪽 포인터 시작부터 끝까지 : n 번 이동

오른쪽 포인터 시작부터 끝까지: n 번 이동

총 이동 횟수는 n+n = 2n 으로, 시간 복잡도는 O(n)

각 포인터가 뒤로 돌아가거나, 동일한 인덱스를 여러 번 방문하지 않음

각 포인터는 배열범위내에서 한 방향으로만 움직이는 전체 배열 크기 n 에 비례하는 선형적 방문만 이뤄짐

for 문안에 while() 이 있어도 시간 복잡도 O(n)인 이유

for 문에서 n 번 돌고 + while도 선행적으로 n번 => 뒤로 돌아가지 않음 n *2 = 2n 번

상수는 빠지게 되므로 O(n)이 된다.

for (int rt = 0; rt < numArr.length; rt++) {
    sum += numArr[rt];
    if(sum==searchNum){
       answer++;
    }
    while (sum>=searchNum){
      sum-=numArr[lt++];
      if(sum==searchNum)answer++;
    } 
 }

다중포문은 다시 돌아가서 돌기때문에 n*n 이 되는것이다.

알고리즘 공부 순서

입출력 - 2442, 2446

DP - 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

정렬 - 2751, 11650, 11651, 10814, 10825, 10989, 11652, 11004

스택 - 10828, 9012, 10799

큐 - 10845

덱 - 10866

문자열 처리 - 10808, 10809, 10820, 2743, 11655, 10824, 11656

기타 자료 구조 - 1406, 1158, 1168

기초 수학 - 10430, 2609, 1934, 1850, 9613, 11005, 2745, 1373, 1212, 2089, 11576, 1978, 1929, 11653, 10872, 1676, 2004, 6588

그래프 - 1260, 11724, 1707, 10451, 2331, 9466, 2667, 4963, 7576, 2178, 2146, 1991, 11725, 1167, 1967

이분탐색/삼분탐색 - 1654, 2805, 2110, 10815, 10816, 11662

분할정복 - 11728, 1780, 11729, 1992, 2447, 2448, 1517, 2261

그리디 - 11047, 2875, 10610, 1783, 1931, 11399, 2873, 1744

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143