알고리즘/시간_공간복잡도1 시간_공간복잡도 시간복잡도 재귀에서의 시간복잡도 재귀도 반복문이랑 동일한 개념을 가지고 있다 형태만 다를뿐이다 변형과 추가된 재귀의 시간복잡도에 대해서 살펴보자 int solve(int n) { if (n < 1) return 0; solve(n / 2); } 위의 시간복잡도는 o(logN)이다 이유는 n이 100이있다고 생각했을 때, 100 50 25.. 반씩 쪼개시기때문이다. 위에서 만약 solve(n . 3)으로한다면 어떻게 될까? 똑같이 o(lognN)이다. 이유는 long3N인데 밑을 지워서 보면 그렇다. 재귀안에서 두번의 호출 int solve(int n) { if (n < 1) return 0; return solve(n - 1) + solve(n - 1); } 위의 상태에서 시간복잡도는 어떻게 될까? 재귀.. 2021. 12. 15. 이전 1 다음