혼자 알고리즘 공부 중입니다. <div><br></div> <div>원서 보고 공부 중인데 거기서 나온 문제입니다.</div> <div><br></div> <div>시간 복잡도 계산이 헷갈려서 질문 드립니다.</div> <div><br></div> <div>아래에 있는 것이 문제이고, <span style="font-size:9pt;line-height:1.5;">수도코드입니다.</span></div> <div><br></div> <div>//울타리의 판자를 모두 색칠하기</div> <div>Algorithm2 (int first_board, int last_<span style="font-size:9pt;line-height:1.5;"> board)</span></div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>if ( first_board == last_board)</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>// 보드가 하나 밖에 없으므로 색칠함</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>paint();</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>else</div> <div> <span class="Apple-tab-span" style="white-space:pre;"> </span>        // 보드들을 반으로 나누기</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>int middle_board = ( first_board + last_board ) / 2</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>Algorithm2 (first_board, middle_board)</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>Algorithm2 (middle_board, last_board)</div> <div>End Algorithms2</div> <div><br></div> <div>해설의 정답은 O(logN + N) = O(N) 입니다.</div> <div><br></div> <div>둘로 나누는 횟수 logN + paint 횟수 N 를 더해 O(logN + N) 이 나왔고 그건 O(N)이 됩니다.</div> <div><br></div> <div>궁금한것은 처음이 왜 O( logN+N)이냐는 것입니다. 특히 logN이요.</div> <div><br></div> <div>재귀함수의 호출 횟수는  logN번이 아니라 더 많이 수행하지 않나요?</div> <div><br></div> <div>ex) <span style="font-size:9pt;line-height:1.5;">N=8이면</span></div> <div><br></div> <div>8 - 4 - 2 - 1</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>      - 1</div> <div>        - 2  - 1</div> <div>               -1</div> <div>   - 4 <span style="font-size:9pt;line-height:1.5;">- 2 - 1</span></div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>      - 1</div> <div>        - 2  - 1</div> <div><span style="font-size:9pt;line-height:1.5;">               -1</span> </div> <div><br></div> <div>이렇게 나누어 질텐데요. 8에서 1로 나눠지기까지 step의 수가 log8 = 3인건 알겠습니다.</div> <div><br></div> <div>근데 재귀 함수가 호출된 횟수는 2*2*2 = 8 이니까요. 왜 재귀함수의 호출 수가 아닌 step의 수인 logN을 시간복잡도로 쓸까요?</div> <div><br></div> <div>궁금합니다. </div>