슬라이딩 윈도우 관련 문의드립니다.

Question

function solution1 ( k , arr ){ let answer , sum = 0 , max = Number . MIN_SAFE_INTEGER for ( let i = 0 ; i <= arr . length - k ; i ++) { answer = [... arr ]. slice ( i , i + k ) sum = answer . reduce (( a , b ) => a + b ) if ( max < sum ) max = sum } return max ; } 섹션 4에서 투포인터 알고리즘 관련해서는 시간복잡도에서 얼마나 단축되는지 이해가 됬는데 이번 슬라이딩 윈도우에서 설명하신 방식에서는 어느 정도로 차이가 나는지 궁금해서 문의글 올립니다. 겉보기엔 for문이 하나인데 reduce에서 배열 합산을 하면서 이중 for문이 들어간 것과 동일하다고 생각하고 드리는 문의사항인데요. 이중 for문을 돌릴 경우의 시간복잡도에 대해 강의 앞부분에서 설명주시긴 했는데, 투포인터 알고리즘 때와 다르게 눈에 띄게 큰 차이를 느끼기가 어려워서 배열을 한 칸씩 이동하면서 잘라서 합산하는 방식이랑 기존의 합산된 것을 새로 더하고 빼는 것이 어느정도로 차이나는지가 궁금합니다.

김태원 · Answer

안녕하세요^^ 위에 코드는 reduec가 answer 길이 만큼 반복하면서 콜백함수를 반복호출하는 구조이기 때문에 2중 for문을 쓰는 시간복잡도 O(n^2)입니다. 영상에서는 for i 가 arr의 길이만큼 반복하면 끝나기 때문에 시간복잡도 O(n) 입니다.