시간복잡도에 관해서!

Question

안녕하세요! 선생님 덕분에 많이 배우고 있습니다. 질문이 굉장히 많은데 모든 질문에 답변해주셔서 매우 놀라고 기뻤습니다..! const solution = function (arr, m) { let cnt = 0; for (let lt = 0; lt < arr.length; lt++) { let sum = arr[lt], rt = lt; while (sum <= m) { cnt++; sum += arr[++rt]; } } return cnt; } console.log(solution([1, 3, 1, 2, 3], 5)); // 10 console.log(solution([1, 1, 1, 1], 5)); // 10 console.log(solution([10, 5, 2, 6], 100)); // 10 강의 듣기 전에 풀어본 것인데 혹시 반례가 있을까요? 그리고 제가 생각했을 때 이 코드의 반복문 실행 횟수가 가장 많아지는 경우는 입력된 수열이 [1, 1, 1, 1] 처럼 모든 요소를 다 더해도 m을 넘어가지 않는 경우에   for문의 lt가 0 일 때 : while문 반복 실행 횟수 4 (sum = 1일때, 2일때, 3일때, 4일때)   lt가 1일 때: while문 반복 횟수 3 (sum = 1, 2, 3)   lt가 2일 때: while문 반복 횟수 2 (sum = 1, 2)   lt가 3일 때: while문 반복 횟수 1 (sum = 1)   이렇게 되니까 입력된 수열의 길이가 n이라 하면 최악에 경우에 실행 횟수는 n + n - 1 + n - 2 + ... + 1 n + n - 1 + n - 2 + ... + 1 (lt = 0일떄 while실행횟수 ~ 마지막) 1 + 2 + 3 + ... + n (lt = arr.length-1일때 while ~ 처음) ------------------------- n * (n + 1)   이니까 총 실행 횟수는 (n^2 + n) / 2 여기서 최고차항 뺴고 다 없애고 계수도 없애면 n^2이니까 시간복잡도는 O(n^2) 이라고 생각했는데 제가 시간복잡도를 맞게 구한걸까요?   반면에 선생님의 코드는 가장 반복 횟수가 많아지는 경우가 제가 고민해봤을 떄 입력된 수열의 길이가 n일때, n -1 번째까지는 다 더해도 m을 안 넘는데 마지막꺼 더했을 때 m을 넘어가는 경우일 것 같은데.. 잘 모르겠어요. 이 경우가 맞을까요? 그럼 이 경우는 for문의 rt가 0에서 마지막 요소까지 쭉 가다가 (실행횟수 = 요소의 갯수 = n번) 마지막 요소에서 와일문이 rt = 0부터 마지막 요소까지 실행되니까 총 2n번 실행되는게 최대 반복 횟수일거같은데 제가 생각한 것이 맞는지 궁금합니다. 그리고 선생님처럼 이렇게 푸는 방법은 솔직히 제 머리론 죽었다 꺠어나도 못떠올릴거같은데 문제를 많이 풀다보면 머리가 좋아질까요..?

김태원 · Answer

안녕하세요^^ 위에 제이슨님 코드는 O(N^2)의 시간복잡도를 갖습니다. 알고리즘을 처음부터 잘 하는 사람은 없습니다. 문제를 많이 풀고 경험하다 보면 실력자가 되어 있을 겁니다.  화이팅하세요^^